数据结构-单链表

一般使用带头结点的单链表。有头结点，head->next是第一个数据。链表操作一般需要借助一两个中间指针，不直接操作传递的参数。函数内修改L的内容，函数参数则用隐式指针&L，取L的地址；不修改内容，只调用数据，函数参数则用L。对于使用了L->next;不需要&L，因为没有修改L，改的是L->next。

两种传参与调用

int InitList(SqList *L)
{
    L->length = 0;
    return 1;
}
InitList(&L);

隐式指针&L

int InitList(SqList &L)
{
    L.length = 0;
    return 1;
}
InitList(L);

int GetElem(LinkList L, int i, int *e)
{
	////
    *e = p->data;     /*  取第i个元素的数据 */
    return 1;
}
GetElem(L, 5, &e);

int GetElem(LinkList L, int i, int &e)
{
	////
    e = p->data;     /*  取第i个元素的数据 */
    return 1;
}
GetElem(L, 5, e);

链表模拟栈

// 车厢调度问题，用不带头结点的单链表描述站台结构
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

struct StackNode
{
    int data;
    struct StackNode *next;
};
typedef struct StackNode *Stack;

int InitStack(Stack &S)
{
    S = NULL;
    return 0;
}
int push(Stack &S, int data)
{
    struct StackNode *p = new StackNode;
    p->data = data;
    p->next = S; //头插法
    S = p;
    return 0;
}
int top(const Stack &S)
{
    return S->data; //出栈
}
void pop(Stack &S)
{
    Stack p = S;
    S = S->next;
    delete p; //移除
}
int empty(const Stack &S)
{
    return S == NULL; //返回0或1
}
int DestroyStack(Stack &S)
{
    while (S != NULL)
    {
        Stack p = S;
        S = S->next;
        delete p;
    }
    //或者
    //pop(S);
    return 0;
}
int main()
{
    int command, n = 1, m;
    Stack S;
    InitStack(S);
    //先进后出
    cout << "请输入进出栈命令: 0表示车厢进站；1表示车厢出站" << endl;
    while (cin >> command)
    {
        if (command == 0)
        {
            if (push(S, n) != 0)
                cout << "站台已满！" << endl;
            else
            {
                cout << "车厢 " << n << " 运货进入站台。" << endl;
                n++;
            }
        }
        else if (command == 1)
        {
            if (empty(S))
                cout << "站台上没有车厢！" << endl;
            else
            {
                m = top(S);
                pop(S);
                cout << "车厢 " << m << " 运货出站。" << endl;
            }
        }
    }
    DestroyStack(S);
    return 0;
}

线性表

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef char DataType;
#define ListSize 10

typedef struct
{
    DataType list[ListSize];
    int length;
} SeqList;

void InitList(SeqList *L)
/*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/
{
    L->length = 0; /*把线性表的长度置为0*/
}
int ListEmpty(SeqList L)
/*判断线性表是否为空，线性表为空返回1，否则返回0*/
{
    if (L.length == 0) /*判断线性表的长度是否为9*/
        return 1;      /*当线性表为空时，返回1；否则返回0*/
    else
        return 0;
}
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/
{
    if (i < 1 || i > L.length) /*在查找第i个元素之前，判断该序号是否合法*/
        return -1;

    *e = L.list[i - 1]; /*将第i个元素的值赋值给e*/
    return 1;
}
int LocateElem(SeqList L, DataType e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/
{
    for (int i = 0; i < L.length; i++) /*从第一个元素开始比较*/
        if (L.list[i] == e)
            return i + 1;
    return 0;
}
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/
{
    if (i < 1 || i > L->length + 1) /*在插入元素前，判断插入位置是否合法*/
    {
        printf("插入位置i不合法！\n");
        return -1;
    }
    else if (L->length >= ListSize) /*在插入元素前，判断顺序表是否已经满，不能插入元素*/
    {
        printf("顺序表已满，不能插入元素。\n");
        return 0;
    }
    else
    {
        for (int j = L->length; j >= i; j--) /*将第i个位置以后的元素依次后移*/
            L->list[j] = L->list[j - 1];
        L->list[i - 1] = e; /*插入元素到第i个位置*/
        L->length++;        /*将顺序表长增1*/
        return 1;
    }
}
int DeleteList(SeqList *L, int i, DataType *e)
{
    if (L->length <= 0)
    {
        printf("顺序表已空不能进行删除!\n");
        return 0;
    }
    else if (i < 1 || i > L->length)
    {
        printf("删除位置不合适!\n");
        return -1;
    }
    else
    {
        *e = L->list[i - 1];
        for (int j = i; j <= L->length - 1; j++)
            L->list[j - 1] = L->list[j];
        L->length--;
        return 1;
    }
}
int ListLength(SeqList L)
{
    return L.length;
}
void ClearList(SeqList *L)
{
    L->length = 0;
}

头插法

有头结点的头插法

int InitStudentList(StudentList &L)
{
    L = new StudentNode;
    L->next = NULL;
    return 0;
}
头插法，头结点不变，可以直接使用L->next，不需要引入中间指针。
int Insert(StudentList L, Student aStudent)
{
    if (L == NULL)
        return 1;
    struct StudentNode *q = new StudentNode; // 创建结点
    q->data = aStudent;
    // 将结点插入指定结点的后面
    q->next = L->next;
    L->next = q;
    return 0;
}

无头结点的头插法

int InitStudentList(StudentList &L)
{
    L = NULL;
    return 0;
}
//头插法，必须是&L，取址！L改变了！！
int Insert(StudentList &L, struct Student aStudent)
{
    struct StudentNode *q = new StudentNode;
    q->data = aStudent;
    q->next = L; // 将新结点插入表头
    L = q;       //L还是头结点
    return 0;
}

建立单链表

头插法建立单链表

void CreateListHead(LinkList *L, int n)
{
    *L = (LinkList)malloc(sizeof(Node)); //头结点
    (*L)->next = NULL;

    for (int i = 0; i < n; i++)
    {
        LinkList p = (LinkList)malloc(sizeof(Node)); // 生成新结点
        p->data = i*i;
        p->next = (*L)->next;
        (*L)->next = p;
    } // 从后往前生成结点，头结点往左运动。
}

尾插法建立单链表

void CreateListTail(LinkList *L, int n)
{
    *L = (LinkList)malloc(sizeof(Node));
    LinkList r = *L;

    for (int i = 0; i < n; i++)
    {
        LinkList p = (Node *)malloc(sizeof(Node));
        p->data = i*i;
        r->next = p;
        r = p; // r后移
    }
    r->next = NULL;
}

单链表基本操作

#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct Node
{
    int data;
    struct Node *next;
} ListNode, *LinkList;//单链表类型定义，一个是结点，一个是链表。

void InitList(LinkList L)
/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/
{
    L = (LinkList)malloc(sizeof(ListNode));
    L->next = NULL; //L->next 是第一个元素
}
/*在单链表中第i个位置插入一个结点，结点的元素值为e。插入成功返回1，失败返回0*/
int InsertList(LinkList L, int i, int e)
{
    int j = 0;
    ListNode *p = L;                     //指针p指向头结点
    while (p->next != NULL && j < i - 1) //找到第i－1个结点，即第i个结点的前驱结点
    {
        p = p->next;
        j++;
    }
    if (!p) //如果没找到，说明插入位置错误
    {
        printf("插入位置错");
        return 0;
    }
    /*新生成一个结点，并将e赋值给该结点的数据域*/
    ListNode *q = (ListNode *)malloc(sizeof(ListNode));
    q->data = e;
    /*插入结点操作*/
    q->next = p->next;
    p->next = q;
    return 1;
}
//借助新指针p计算长度，不然链表指针L会指向结尾。
int ListLength(LinkList L)
{
    int count = 0;
    ListNode *p = L;
    while (p->next != NULL)//L->next 是第一个元素
    {
        p = p->next;
        count++;
    }
    return count;
}
int ListEmpty(LinkList L)
{
    if (L->next == NULL) //L->next 是第一个元素
        return 1;        /*当单链表为空时，返回1；否则返回0*/
    else
        return 0;
}

ListNode *Get(LinkList L, int i)
/*查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败。*/
{
	if (ListEmpty(L)) /*在查找第i个元素之前，判断链表是否为空*/
        return NULL;
    if (i < 1) /*在查找第i个元素之前，判断该序号是否合法*/
        return NULL;

    ListNode *p = L;
    int j = 0;
    while (p->next != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    if (j == i)
        return p; /*找到第i个结点，返回指针p*/
    else
        return NULL; /*如果没有找到第i个元素，返回NULL*/
}

void DisplayList(LinkList L) /*输出链表*/
{
    int n = ListLength(L);
    for (int i = 1; i <= n; i++) /*输出单链表L中的每个元素*/
    {
        ListNode *p = Get(L, i); /*返回单链表L中的每个结点的指针*/
        if (p)
            printf("%d\t", p->data); /*输出单链表L中的每个元素*/
    }
}
void PrintList(LinkList L) // 输出链表上各结点的数据
{
    printf("链表上各结点的数据为：\n");
    for (LinkList p = L->next; p != NULL; p = p->next)
        printf("%d  ", p->data);
    printf("\n");
}
/*逆置链表*/
void ReverseList(LinkList L)
{
    ListNode *p = L->next; /*p指向链表的第一个结点*/
    L->next = NULL;
    while (p) /*利用头插法将结点依次插入到链表的头部*/
    {
        ListNode *q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

ListNode *LocateElem(LinkList L, int e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败。*/
{
    ListNode *p = L->next; /*指针p指向第一个结点*/
    while (p)
    {
        if (p->data != e) /*找到与e相等的元素，返回该序号*/
            p = p->next;
        else
            break;
    }
    return p;//查找成功将对应元素的结点指针返回，否则返回NULL表示失败。
}
int LocatePos(LinkList L, int e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/
{
    if (ListEmpty(L)) /*在查找第i个元素之前，判断链表是否为空*/
        return 0;

	ListNode *p = L->next; /*指针p指向第一个结点*/
    int i = 1;
    while (p)
    {
        if (p->data == e) /*找到与e相等的元素，返回该序号*/
            return i;
        else
        {
            p = p->next;
            i++;
        }
    }
    if (!p) /*如果没有找到与e相等的元素，返回0，表示失败*/
        return 0;
    return 0;
}

int DeleteList(LinkList L, int i, int *e)
/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/
{
    int j = 0;
    ListNode *pre = L;
    while (pre->next != NULL && pre->next->next != NULL && j < i - 1) /*判断是否找到前驱结点*/
    {
        pre = pre->next;
        j++;
    }
    if (j != i - 1) /*如果没找到要删除的结点位置，说明删除位置错误*/
    {
        printf("删除位置错误");
        return 0;
    }
    /*指针p指向单链表中的第i个结点，并将该结点的数据域值赋值给e*/
    ListNode *p = pre->next;
    *e = p->data;
    /*将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/
    pre->next = p->next;
    free(p); /*释放p指向的结点*/
    return 1;
}

void DestroyList(LinkList L)
{
    ListNode *p = L, *q;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
}
void MergeList(LinkList A, LinkList B, LinkList *C)
/*单链表A和B中的元素非递减排列，将单链表A和B中的元素合并到C中，C中的元素仍按照非递减排列*/
{
    ListNode *pa, *pb, *pc; /*定义指向单链表A，B,C的指针*/
    pa = A->next;
    pb = B->next;
    *C = A; /*将单链表A的头结点作为C的头结点*/
    (*C)->next = NULL;
    pc = *C;
    /*依次将链表A和B中较小的元素存入链表C中*/
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa; /*如果A中的元素小于或等于B中的元素，将A中的元素的结点作为C的结点*/
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb; /*如果A中的元素大于B中的元素，将B中的元素的结点作为C的结点*/
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb; /*将剩余的结点插入C中*/
    free(B);                 /*释放B的头结点*/
}

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    LinkList L;
    InitList(L);
    for (int i = 1; i <= 10; i++)    /*将数组a中元素插入到单链表L中*/
        InsertList(L, i, a[i - 1]); //插入到第i个位置

    PrintList(L);
    DisplayList(L);
    return 0;
}

struct List
{
    int data;
    struct List *next;
};
//创建表头的过程
struct List *createList()
{
    struct List *headNode = (struct List *)malloc(sizeof(struct List));
    headNode->next = NULL;
    //headNode->data 表头特殊，不用数据域，作为差异性
    return headNode;  //可以返回头结点
}
//插入结点,头插法
void inserListByHead(struct List *headNode, int data)
{
    //插入前首先得创建插入的结点
    struct List *newNode = (struct List *)malloc(sizeof(struct List));
    newNode->data = data;
    //实现插入
    newNode->next = headNode->next;
    headNode->next = newNode;
}
//删除结点，指定位置删除
void deleteByAppoin(struct List *headNode, int data)
{
    struct List *p = headNode;
    struct List *q = headNode->next;
    if (q == NULL)
    {
        printf("无可用数据,表空\n");
        return;
    }
    while (q->data != data)
    {
        
        p = q;//后移
        q = p->next; //也就是q->next;
        if (q == NULL)
        {
            printf("未找到相关信息，无法删除\n");
            return;
        }
    }
    p->next = q->next;
    free(q);
}

typedef struct node //定义结点结构
{
    int data;
    struct node *next;
} LNode, *LinkList; // 结点类型名LNode，指针类型名LinkList

//尾插法
void CreateListRear(LinkList L, int n) /* L为带头结点空链表，且头结点已存在。*/
{
    LinkList p = L; //指针p指向头结点；
    for (int i = 0; i < n; i++)
    {
        LinkList q = (LinkList)malloc(sizeof(LNode));
        q->data = i * i;
        p->next = q; // 将新节点q作为p的后继;
        p = q;       //让p指向新的表尾结点q；
    }
    p->next = NULL; // p的next域赋值为NULL
}

头插法；插入到头结点后面

struct studentCard *insertLink(struct studentCard *head, int number, struct studentCard *node)
{
    struct studentCard *p = head;
    if (p == NULL)
        printf("该链表为空");
    while (p)
    {
        if (p->cardnum == number)
        {
            node->next = p->next; //插到p后面
            p->next = node;
            break;
        }
        else
            p = p->next;
    }
    return head; //仍然返回头结点
}

删除

struct studentCard *deleLink(struct studentCard *head, int number)
{
    struct studentCard *p = head;
    if (p->cardnum == number) //如果删除的是头结点
    {
        head = p->next;
        free(p);
    }
    //删除的不是头结点
    struct studentCard *q = p->next;
    while (q->cardnum != number && q->next != NULL)
    {
        p = q;
        q = q->next;
    }
    if (q->cardnum == number)
    {
        p->next = q->next;
        free(q);
    }
    return head;
}

链表管理学生的借书卡信息

struct studentCard
{
    int cardnum;
    char studentname[10];
    struct studentCard *next;
};
int main(void)
{
    int i = 0, number;
    char name[10];
    struct studentCard *head = NULL, *p;
    printf("输入10个学生的借书卡信息：\n卡号\t姓名\n");
    while (i < 3)
    {
        scanf("%d%s", &number, name);
        p = (struct studentCard *)malloc(sizeof(struct studentCard));
        p->cardnum = number;
        strcpy(p->studentname, name);
        p->next = head; //头插法
        head = p;
        i++;
    }
    printf("\n输出学生借书卡信息\t\n卡号\t姓名\n");
    while (p)
    {
        printf("%d\t%s\n", p->cardnum, p->studentname);
        p = p->next;
    }
    return 0;
}

链表的插入排序

void InsertSort(LinkList L)
{
    ListNode *p = L->next;
    L->next = NULL;   /*初始时，已排序链表为空*/
    while (p != NULL) /*p是指向待排序的结点*/
    {
        if (L->next == NULL) /*如果*p是第一个结点，则插入到L，令已排序的最后一个结点的指针域为空*/
        {
            L->next = p;
            p = p->next;
            L->next->next = NULL;
        }
        else /*p指向待排序的结点，在L指向的已经排好序的链表中查找插入位置*/
        {
            ListNode *pre = L;
            ListNode *q = L->next;
            while (q != NULL && q->data < p->data) /*在q指向的有序表中寻找插入位置*/
            {
                pre = q;
                q = q->next;
            }
            q = p->next;         /*q指向p的下一个结点，保存待排序的指针位置*/
            p->next = pre->next; /*将结点*p插入到结点*pre的后面*/
            pre->next = p;
            p = q; /*p指向下一个待排序的结点*/
        }
    }
}

对链表L排序

void ListOrder(LinkList L)
{
    ListNode *p, *r, *t, *q;
    p = L->next;      /*p是指向待排序的结点的第一个结点*/
    L->next = NULL;   /*初始时，已排序链表为空*/
    while (p != NULL) /*如果待排序链表不为空*/
    {
        if (L->next == NULL) /*如果是第一个结点，则作为第一个结点插入L*/
        {
            L->next = p;
            r = p->next;
            p->next = NULL;
            p = r;
        }
        else /*p指向待排序的结点，在L指向的已经排好序的链表中查找插入位置*/
        {
            r = L;
            q = L->next;
            while (q != NULL && p->data > q->data) /*在q指向的有序表中寻找插入位置*/
            {
                r = q;
                q = q->next;
            }
            t = p->next;       /*t指向p的下一个结点，保存待排序的指针位置*/
            p->next = r->next; /*将结点*p插入到结点*r的后面*/
            r->next = p;
            p = t; /*p指向下一个待排序的结点*/
        }
    }
}

双链表，环

typedef struct DualNode
{
    char data;
    struct DualNode *prior;
    struct DualNode *next;
} DualNode, *DuLinkList;

int InitList(DuLinkList *L)
{
    *L = (DuLinkList)malloc(sizeof(DualNode));
    (*L)->next = (*L)->prior = NULL;

    DualNode *p = *L;

    for (int i = 0; i < 26; i++)
    {
        DualNode *q = (DualNode *)malloc(sizeof(DualNode));
        q->data = 'A' + i;

        q->next = p->next;
        p->next = q;
        q->prior = p;
        p = q;
    }
    p->next = (*L)->next; //环
    (*L)->next->prior = p;
    return OK;
}
InitList(&L);

typedef struct node
{
    int data;
    struct node *next;
} sqlist, *linklist;

linklist CreateLinkList()
{
    linklist head = NULL;
    linklist r = head;
    for (int i = 1; i <= CardNumber; i++)
    {
        linklist s = (linklist)malloc(sizeof(sqlist));
        s->data = 0;
        if (head == NULL)
            head = s;
        else //尾插法
            r->next = s;
        r = s;
    }
    r->next = head; //形成环
    return head;
}

利用快慢指针的方法判断是否循环链表。

int HasLoop2(LinkList L)
{
    int step1 = 1;
    int step2 = 2;
    LinkList p = L;
    LinkList q = L;

    while (p != NULL && q != NULL && q->next != NULL)
    {
        p = p->next;
        if (q->next != NULL)
            q = q->next->next;
        printf("p:%d, q:%d \n", p->data, q->data);
        if (p == q)
            return 1;
    }
    return 0;
}