线性表代码总结

文章目录

1. 线性表的结构体定义1.1 顺序表的结构体定义1.2 单链表结点定义1.3 双链表结点定义 2. 顺序表的操作2.1 按元素值的查找算法2.2 插入数据元素2.3 删除数据元素 3. 单链表的操作3.1 尾插法建立单链表3.2 头插法建立单链表3.3 合并两个单链表3.4 查找结点是否存在 4. 双链表的操作4.1 尾插法建立双链表4.2 查找结点4.3 插入结点4.4 删除结点 5. 常见习题

1. 线性表的结构体定义

1.1 顺序表的结构体定义

#define maxSize 100 //整型常量

typedef struct{ int data[maxSize]; //存放顺序表元素的数组 int length; //存放顺序表的长度 }SqList; //顺序表类型定义

但考试使用最多的顺序表的定义如下：

int A[maxSize]; int n;

如上两行定义了一个长度为n，表内元素为整数的顺序表。

1.2 单链表结点定义

typedef struct LNode{ int data; //data中存放结点数据域 struct LNode *next; //指向后继结点的指针 }LNode； //定义单链表结点类型

1.3 双链表结点定义

typedef struct DLNode{ int data; struct DLNode *prior; //指向前驱结点的指针 struct DLNode *next; //指向后继结点的指针 }DLNode;

什么是结点？ 结点即内存中由用户分配的一块空间，只有一个地址来表示结点的存在与否，所以在为链表分配空间的时候，会同时定义一个指针，存储这片空间的地址（即指针指向结点），并将此指针名称作为结点的名称。

LNode *addr=(LNode*）malloc(sizeof(LNode));

即分配了一片LNode型空间，也就是一个LNode型结点。并定义一个名为addr的指针指向这个结点。同时，addr也作为该结点的名字。addr命名包含两个东西：第一，结点；第二，是指向这个结点的指针。

2. 顺序表的操作

2.1 按元素值的查找算法

/** 查找第一个值等于e的元素，并返回其下标 */ int findElem(SqList L,int e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i; //找到，返回下标 return -1; //未找到，返回-1,作为失败标志 }

2.2 插入数据元素

/** 顺序表的第p个位置插入新的元素e */ int insertElem(SqList &L,int p,int e){ //L本身要改变，采用引用 if(p<0||p>L.length||L.length==maxSize) //插入位置不合法 return 0; for(int i=L.length-1;i>=p;i--) L.data[i+1]=L.data[i]; //从p开始元素后移 L.data[p]=e; //将元素e插入到位置p上 ++(L.length); return 1; //插入成功，返回1 }

2.3 删除数据元素

/** 删除表中下标为p的元素，成功返回1，否则返回0，并将删除的元素赋值给e */ int deleteElem(SqList &L,int p,int &e){ if(p<0||p>L.length) return 0; e=L.data[p]; //将被删除的元素赋值给e for(int i=p;i<L.length-1;i++) //从p位置开始，将后边元素前移 L.data[i]=L.data[i+1]; --(L.length); //表长减1 return 1; }

3. 单链表的操作

3.1 尾插法建立单链表

/** n个元素存储在数组a中，尾插法建立链表C */ void createListT(LNode *&C,int a[],int n){ LNode *s,*r; //s指向新申请的结点，r始终指向C的终端结点 C=(LNode*)malloc(sizeof(LNode)); //申请头结点空间 C->next=NULL; r=C; //r指向头结点,此时头结点即是终端结点 for(int i=0;i<n;i++){ s=(LNode*)malloc(sizeof(LNode)); //s指向新申请的结点 s->data=a[i]; r->next=s; //用r来接纳新结点 r=r->next; //r指向终端结点,以便接受新的结点 } r->next=NULL; //终端结点指针域置空，链表建立完成 }

3.2 头插法建立单链表

void createListH(LNode *&C,int a[],int n){ LNode *s; C=(LNode*)malloc(sizeof(LNode)); //申请头结点空间 C->next=NULL; for(int i=0;i<n;i++){ s=(LNode*)malloc(sizeof(LNode)); s->data=a[i]; s->next=C->next; //s所指新结点指针域next指向C中的开始结点 C->next=s; //头结点的指针域next指向s结点，使得s称为新的开始结点 } }

该算法不断将新结点插入到链表前端，因此新建立的链表中元素的次序和数组a中元素的次序是相反的。

3.3 合并两个单链表

/** A,B两个递增单链表（带头结点），将其归并成一个按元素值非递减 有序的链表C。 */ void merge(LNode *A,LNode *B,LNode *&C){ LNode *p=A->next; // LNode *q=B->next; // LNode *r; //r始终指向C的终端结点 C=A; //用A的头结点作为C的头结点 C->next=NULL; //从A链表取下头结点作为新链表的头 free(B); //B的头结点已无用，释放 r=C; //r指向C，此时头结点也是终端节点 while(p!=NULL&&q!=NULL){ if(p->data<=q->data){ r->next=p; p=p->next; r=r->next; } else{ r->next=q; q=q->next; r=r->next; } } if(p!=NULL) r->next=p; //将p剩余元素连接在新链表中 if(q!=NULL) r->next=q; //同上句 }

3.4 查找结点是否存在

/** 查找链表（带头结点）中是否存在一个值为x的结点，存在，则删除返回1，否则返回0 */ int findAndDelete(LNode *C,int x){ LNode *p,*q; p=C; while(p->next!=NULL){ if(p->next->data==x) break; p=p->next; } if(p->next==NULL) //查找结束 return 0; else{ /*删除部分*/ q=p->next; p->next=p->next->next; free(q); return 1; } }

4. 双链表的操作

4.1 尾插法建立双链表

void createDListT(DLNode *&L,int a[],int n){ DLNode *s,*r; L=(DLNode*)malloc(sizeof(DLNode)); L->prior=NULL; L->next =NULL; r=L; //r始终指向终端结点，开始时头结点就是尾结点 for(int i=0;i<n;i++){ s=(DLNode*)malloc(sizeof(DLNode)); //创建新结点 s->data=a[i]; //将s插入到L的尾部，并且r指向s， r->next=s; s->prior=r; r=s; } r->next=NULL; }

4.2 查找结点

/** 查找双链表中第一个值为x的结点，找到返回结点指针，否则返回NULL */ DLNode* findNode(DLNode *C,int x){ DLNode *p=C->next; while(p!=NULL){ if(p->data==x) break; p=p->next; } return p; //若找到，p中内容是结点地址，没找到，p中内容为NULL }

4.3 插入结点

/** p所指的结点之后插入一个结点s */ s->next=p->next; s->prior=p; p->next=s; s->next->prior=p; //若p指向的结点是最后一个结点，不需要此行

4.4 删除结点

/** 删除双链表中p结点的后继 */ q=p->next; p->next=q->next; p->next->prior=p; free(q);

5. 常见习题

1. 递归删除不带头结点的单链表L中所有值为x的结点

/** f(L,x):删除以L为首结点指针的单链表中所有值等于x的结点， 终止条件：L为空表 递归主体：f(L,x)=删除*L结点；f(L->next,x); 若L->data==x; f(L,x)=f(L->next,x); 其他情况 */ void Del_x(LinkList &L,ElemType x){ //递归删除单链表L中值为x的结点 LNode *p; //p指向待删除结点 if(p==NULL) //递归出口 return; if(L->data==x){ //L所指的结点值为x p=L; //删除*L，并让L指向下一个结点 L=L->next; free(p); Del_x(L,x); //递归调用 } else //L所指结点不为x Del_x(L->next,x); //递归调用 }

因为需要借助一个递归工作栈，深度为O(n),时间复杂度为O(n).

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

/** 第一中解法： 用p从头扫描单链表，pre指向*p结点的前驱。若p指向的结点值为x， 则删除，并让p移向下一个结点,否则p，pre同时后移一个结点 */ void Del_x(LinkList &L,ElemType x){ //L为带头结点的单链表，删除该链表中所有值为x的结点 LNode *p=L->next,*pre=L,*q; // while(p!=NULL){ if(p->next==x){ q=p; //q指向待删除结点 p=p->next; pre->next=p; //删除*q结点 free(q); } else{ //否则，pre,p同时后移 pre=p; p=p->next; }//else }//while } /** 第二种解法： 采用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x的是否将其链接在L后，否则将其释放 */ void Del_x(LinkList &L,ElemType x){ //L为带头结点的单链表，删除该链表中所有值为x的结点 LNode *p=L->next,*r=L,*q; //r始终指向终端结点 while(p!=NULL){ if(p->data!=x){ r->next=p; r=p; p=p->next; //继续扫描 } else{ //*p结点值不为x时，释放 q=p; p=p->next; //继续扫描 free(q); } }//while }

上述两种算法扫描单链表一趟，时间复杂度为O(n),空间复杂度为O(1).

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

/** 可以用栈的思想来实现，即这里用递归来实现。每访问一个结点时，，先递归输出它后边的结点， 再输出自身结点，这样就完成了链表反转 */ void printR(LinkList L){ if(L->next!=NULL) printR(L->next); //递归调用 print(L->data); //调用输出函数 }

4. 带头结点的单链表L中删除一个最小值结点（唯一）

/** p从头到尾扫描单链表，pre指向p的前驱，用minp保存值最小的结点指针，minpre指向*minp 结点的前驱（初值为pre).若p->data < minp->data,则将p,pre分别赋值给minp,minpre, 当p扫描完毕，minp指向最下结点，minpre指向最小值结点的前驱，再将minp所指结点删除。 */ LinkList Del_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; }//while minpre->next=minp->next; //删除最小值结点 free(minp); return L; }

该算法扫描一趟链表，时间复杂度为O(n),空间复杂度为O(1).

5. 带头结点的单链表原地逆置（原地：辅助空间复杂度为O(1))

/** 将头结点取下，从第一个结点开始，依次插入到头结点后面（头插入建立单链表），直到 最后一个结点为止，即完成要求的逆置 */ LinkList Reverse_H(LinkList 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; //将p结点插入到头结点之后 L->next=p; //L仍然指向第一个结点 p=r; //r赋值给p，方便以便继续循环 } return L; } 将一个带头结点的单链表，使其元素递增有序 /** 直接插入排序，构成只含有一个数据结点的有序单链表，然后依次扫描单链表中剩余结点*p， 在有序表中通过比较查找插入*p的前驱结点*pre,然后将*p插入到*pre之后 */ void Sort(LinkList &L){ LNode *p=L->next,*pre; LNode *r=p->next; //r存储*p后继结点指针，以保证不断链 p-next=NULL; //构造只含一个数据结点的有序表 p=r; while(p!=NULL){ r=p->next; //保存*p的后继结点指针 pre=L; while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next; //有序表中查找插入*p的前驱结点*pre p->next=pre->next; //将*p插入到*pre之后 pre->next=p; p=r; //扫描原单链表剩下结点 } }

7. 删除一个带头节点的单链表中给定区间的元素(若存在),链表无序。

/** 链表无序，只能逐个检查 */ void RangeDel(LinkList &L,int min,int max){ LNode *pre=L,*p=L->next; //p是工作指针，pre是其前驱 while(p!=NULL){ if(p->data>min&&p->data<max){ //找到要删除结点，删除 pre->next=p->next; free(p); p=pre->next; } else{ //否则继续找寻 pre=p; p=p->next; } } }

8. 确定两个单链表的公共结点

LinkList SearchCommon(LinkList L1,LinkList L2){ //线性时间内找到第一个公共结点 int len1=Length(L1),len2-Length(L2); //计算两个链表的表长 LinkList lList,sList; //分别指向较长和较短的链表 if(len1>len2){ lList=L1->next; sList=L2->next; dist=len1-len2; //表长之差 } else{ lList=L2->next; sList=L1->next; dist=len2-len1; } while(dist--) lList=lList->next; //表长的链先遍历到第dist个结点，然后同步 while(lList!=NULL){ //同步寻找共同结点 if(lList==sList) //找到第一个公共结点 return lList; else{ //继续同步寻找 lList=lList->next; sList=sList->next; } }//while return NULL; }

9. 给定带头结点的单链表，按递增次序输出各结点数据元素（不借助辅助空间）

/**思想：对链表进行遍历，每次找到最小值元素，输出并释放结点， 再次进行遍历输出，直到输出完毕 */ void Min_Del(LinkList &head){ //head是带有头节点的单链表的头指针 while(head->next!=NULL){ //循环到仅剩头结点 pre=head; //pre为最小值结点的前驱结点 p=pre->next; //p为工作指针 while(p->next!=NULL){ if(p->next->data<pre->next->data){ pre=p; //记录当前最小值结点的前驱 p=p->next; } }//while print(pre->next->data); //输出元素最小值结点的数据 u=pre->next; //删除元素最小值结点,释放结点空间 pre->next=u->next; free(u); }//while free(head); //释放头结点 }

该算法时间复杂度为O(n*n).

10. 将带头结点的单链表分解为两个带头结点的单链表（分别含有原表中序号为奇数和偶数的元素）

/** 思想：设置一个访问变量，每访问一个序号+1，然后依据序号奇偶性插入到两个表中 */ LinkList DisC(LinkList &L){ //将A表中结点按序号的奇偶性分解到A表和B表中 int i=0; //记录A表中序号 B=(LinkList)malloc(sizeof(LNode)); //创建B表表头 B->next=NULL; //B表初始化 LNode *ra=A,*rb=B; //ra和rb分别指向将创建的A表和B的尾结点 p=A->next; //p为工作指针,指向待分解的结点 A=NULL; //置空新的A表 while(p!=NULL){ i++; if(i%2==0) { rb->next=p; //B表尾插入新结点 rb=p; //指向新的表尾结点 } else{ ra->next=p; ra=p; } p=p->next; //将p指向待要处理的结点 }//while ra->next=NULL; rb->next=NULL; return B; }