线性表——链表

定义

单链表定义

typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList;

双链表定义

typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinkList;

静态链表定义

#define MaxSize 50 //静态链表的最大长度 typedef struct{ //静态链表结构类型定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 }SLinkList[MaxSize];

基本操作

头插法建立单链表

LinkList CreatList1(LinkList &L){ //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素 LNode *s; int x; L = (LinkList)malloc(sizeof(LNode)); //创建头结点 L->next = NULL; //初始为空链表 scanf("%d", &x); //输入结点的值 while(x != 9999){ //输入9999表示结束 s = (LNode *)malloc(sizeof(LNode)); //创建新结点 s->data = x; s->next = L->next; L->next = s; //将新结点插入表中，L为头指针 scanf("%d", &x); } return L; }

尾插法建立单链表

LinkList CreatList2(LinkList &L){ //从表头到表尾正向建立单链表L，每次均在表尾插入元素 int x; //设元素类型为整型 L = (LinkList)malloc(sizeof(LNode)); LNode *s, *r = L; //r为表尾指针 scanf("%d", &x); //输入结点的值 while(x != 9999){ //输入9999表示结束 s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; //r指向新的表尾结点 scanf("%d", &x); } r->next = NULL; //尾结点指针置空 return L; }

按序号查找结点

LNode *GetElem(LinkList L, int i){ //本算法取出单链表L（带头结点）中第i个位置的结点指针 int j = 1; //计数，初始为1 LNode *p = L->next; //头结点指针赋给p if(i == 0) return L; //若i等于0，则返回头结点 if(i < 1) return NULL; //若i无效，则返回NULL while(p && j<i){ //从第1个结点开始找，查找第i个结点 p = p->next; j++; } return p; //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可 }

按值查找表结点

LNode *LocateElem(LinkList L, ElemType e){ //本算法查找单链表L（带头结点）中数据域值等于e的结点指针，否则返回NULL LNode *p = L->next; while(p!=NULL && p->data!=e) //从第1个结点开始查找data域为e的结点 p = p->next; return p; //找到后返回该结点指针，否则返回NULL

插入结点

略…

删除结点

略…

题目

1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点

算法思想：设f(L，x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点，则显然有f(L->next，x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。由此，可以推出递归模型如下： 终止条件：f(L，x)=不做任何事情； 若L为空表 递归主体：f(L，x)=删除*L结点;f(L->next，x); 若L->data=x f(L，x)=f(L->next，x); 其他情况

void Del_X_3(LinkList &L, ElemType x){ //递归实现在单链表L中删除值为x的结点 LNode *p; //p指向待删除结点 if(L == NULL) //递归出口 return; if(L->data == x){ //若L所指结点的值为x p = L; //删除*L，并让L指向下一结点 L = L->next; free(p); Del_X_3(L, x); //递归调用 } else Del_X_3(L->next, x); }

有读者认为直接free掉p结点会造成断链，实际上因为L为引用，是直接对原链表进行操作，因此不会断链。（王道原话）

2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一

解法一：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。

void Del_X_1(LinkList &L, ElemType x){ //L为带头结点的单链表，本算法删除L中所有值为x的结点 LNode *p = L->next, *pre = L, *q; //置p和pre的初始值 while(p != NULL){ if(p->data == x){ q = p; //q指向要被删除的结点 p = p->next; pre->next = p; //删除*q结点 free(q); //释放*q结点的空间 } else{ pre = p; p = p->next; } } //while }

解法二：采用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放

void Del_X_2(LinkList &L, ElemType x){ //L为带头结点的单链表，本算法删除 L中所有值为 x的结点 LNode *p = L->next, *r = L, *q; //r指向尾结点，其初值为头结点 while(p != NULL){ if(p->data != x){ //*p结点值不为x时将其链接到 L尾部 r->next = p; r = p; p = p->next; //继续扫描 } else{ //*p结点值为x时将其释放 q = p; p = p->next; free(q); } } //while r->next = NULL; //插入结束后置尾结点指针为NULL }

3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值

栈 递归

void R_Print(LinkList L){ //从尾到头输出单链表L中每个结点的值 if(L->next != NULL){ R_Print(L->next); //递归 } print(L->data); //输出函数 }

4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）

LinkList Delete_Min(LinkList &L){ //L是带头结点的单链表，本算法删除其最小值结点 LNode *pre = L, *p = pre->next; //p为工作指针，pre指向其前驱 LNode *minpre = pre, *minp = p; //保存最小值结点及其前驱 while(p != NULL){ if(p->data < minp->data){ minp = p; //找到比之前找到的最小值还小的结点 minpre = pre; } pre = p; //继续扫描下一个结点 p = p->next; } minpre->next = minp->next; //删除最小值结点 free(minp); return L; }

5.试编写算法将带头结点的单链表就地逆置，就地，是指空间复杂度为O(1)

解法一：将头结点摘下，然后从第一个结点开始，依次前插入到头结点的后面（头插法建立单链表），直到最后一个结点为止

LinkList Reverse_1(LinkList L){ //L是带头结点的单链表，本算法将L就地逆置 LNode *p *r; //p为工作指针，r为p的后继，以防断链 p = L->next; //从第一个元素结点开始 L->next = NULL; //先将头结点L的next域置为NULL while(p != NULL){ //依次将元素结点摘下 r = p->next; //暂存p的后继 p->next = L->next; L->next = p; p = r; } return L; }

解法二： （未完待续…）