@auther by sizaif
说明：
部分题目为王道题目整理，(ps.王道上思路没问题，在实现代码上略有些问题)
因个人代码风格与王道略有不同，部分细节代码也不尽相同
个人整理by sizaif
@TOC
链表：
//单链表结构
typedef struct link{
int data;
link *next;
}node,*linklist;1) 输入一组整型元素序列，使用尾插法(头插法)建立一个带有头结点(不带头结点)的单链表。
code
/**
* 建立带头结点的单链表
* @param L [description]
*/
void Creat_list_Head(linklist &L)
{
L = new node();
linklist p,s=L;
L->next=NULL;
int x;
/*while(cin>>x,x>0)// 头插
{
p= new node();
p->data =x;
p->next=L->next;
L->next=p;
}*/
while(cin>>x,x>0)//尾插
{
p=new node();
p->data=x;
s->next=p;
s=p;
}
}
void Creat_list_withoutHead(linklist &L){
L = NULL;
linklist p,s;
int x;
/*
while(cin>>x,x>0)// 头插
{
p= new node();
p->data =x;
p->next=L;
L=p;
}
*/
while(cin>>x,x>0){ // 尾插
p = new node();
p->data = x;
p->next = NULL;
if(L==NULL) L = p; // 第一个结点
else{
s = L;
while(s->next){ // 遍历到最后一个结点
s = s->next;
}
s->next = p;
}
}
}2) 在该单链表的第i个元素前插入一个整数。(从0开始)
code
++/** * 在 单链表 第x个位置 前插入y * @param L [description] * @param x [description] * @param y [description] * @return [description] */ void Add_before_X(linklist &L,int x,int y) { linklist p,s; p=L->next; int j=0; while(p&&j<x-1) { p=p->next;j++; } if(!p||j>x-1){cout<<"error"<<endl;return;} s=new node(); s->data=y; s->next=p->next; p->next=s; }
3) 删除该单链表中的第i个元素，其值通过参数将其返回(从0开始)。
code
++/** * 删除单链表中第i个元素 的结点 * @param L [description] * @param i [description] */ void Delet_x(linklist &L,int &i) { linklist s,p; p=L->next; int j=0; while(p&&j<i-1) { p=p->next; j++; } i = p->data; s = p->next; p->next=s->next; }
4) 建立两个按值递增有序的带头结点的单链表，将他们合并成一个按值递减有序的单链表。
code
++/** * 思路： 归并， 头插法 */ linklist Union(linklist la,linklist lb){ linklist p,q,r,rear,t; p = la->next,q = lb->next; la->next = NULL; r = la; // r重构la while( p && q){ if( p->data < q->data){ rear = p->next; p->next = r->next; r->next = p; p = rear; }else if( p->data > q->data){ rear = q->next; q->next = r->next; r->next = q; q = rear; } else { // 当两个值相同时,(按题目要求两个都保留, 另外一个free掉) rear = q->next; t = p ->next; p->next = r->next; r->next = p; q->next = r->next; r->next = q; // free(q); q = rear; p = t; } } while(p){ // 因为是倒叙, 所以必须 逐步遍历头插剩余部分 rear = p->next; p->next = r->next; r->next = p; p = rear; } while(q){ rear = q->next; q->next = r->next; r->next = q; q = rear; } return la; }
plus-两个单调递增有序的单链表A B 合并成一个单调递增有序的单链表C
code
++/** * 两个单调递增有序的单链表A B 合并成一个单调递增有序的单链表C * @param L [description] * @param B [description] */ void Merage_A_B(linklist &A,linklist &B,linklist &C) { linklist pa,pb,pc; pa = A->next; pb = B->next; pc = new node(); pc ->next =NULL; while(pa&&pb) { if(pa->data <= pb->data){ pc->next = pa; pc = pa; pa = pa->next; }else{ pc ->next = pb; pc = pb; pb = pb->next; } } // 尾插 pc ->next = pa? pa:pb; }
5) 试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O(1)。 (计.期末.10.1)
头插重新建表
指针反转
顺序存储 数组
code
++//法一：头插法从新建表 void reverse(linklist &L){ linklist p,rear; // rear 为p的后继 防止断链 p = L->next; L->next = NULL; // 头结点的Next 置为null while(p){ rear = p->next; // 头插法 p->next = L->next; L->next = p; p = rear; } } //法二：指针反转 void reverse(linklist &L){ LinkList temp,p,q; temp = NULL; p = L->next; q = L->next->next; while(q!=NULL){ temp = q->next; // 暂存q-Next q->next = p; // 指针逆置 p = q; // 往后移 q = temp; } L->next->next=NULL; // 第一个结点变成最后一个结点 L->next = p; // 最后一个结点变成第一个结点 } //法三： 顺序存储 数组 void reverse(int A[],int n){ for(int i = 0 ; i < n/2 ; i++){ temp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = temp; } }
6) 将一个头指针为head且不带头节点的单链表改造为一个含头节点且头指针为head的单循环链表 (计.期末.09.1)
code
++//没有单循环-> head->next = head; 改造为带头结点的 void fun(LinkList &head){ LinkList p; p = new LinkNode(); if(head == NULL){ head = p; p->next = p; // 单循环 }else{ p->next = head; // 创造头结点 // 单循环列表 Linklist t = head; while(t->next != NULL){ t = t->next; } t->next = p; // 最后一个结点指向头结点 head = p; // 将p 赋给 head 变成head链表 } }
7) 假设有两个按元素值递增次序排列的线性表，均不带头结点以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减(非递减)次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表 (计.期末.08.2) !!!
code
++linklist merge_without_Head(linklist la,linklist lb){ linklist lc = NULL,lce = NULL; while(la && lb) { if( la->data <= lb->data){ if(!lc) lc = la; else { lce->next = la; } lce = la; la = la->next; }else{ if(!lc) lc = lb; else { lce->next = lb; } lce = lb; lb = lb->next; } } if(lc){ if(la) lce ->next = la; else lce ->next = lb; }else { if(la ) lc = la; else lc = lb; } return lc; }
8) 给定一个带表头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变
code
++void div(linklist &A,linklist &B){ linklist p,pc,pb,temp,Lc; p = A->next; Lc = new node(); Lc->next = NULL; pc = Lc; pb = B; int i = 1; while(p){ temp = p->next; // 保存后继防止断链 if(i%2==1){ //尾插 p->next = pc->next; pc->next = p; pc = p; }else { //尾插 p->next = pb->next; pb->next = p; pb = p; } p = temp; i++; } A = LC; }
9) 设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点(统计值等于x的数目) int CountX(Lnode * HL, ElemType x)
code
++void del(LinkList &L,ElemType x){ LinkList temp; // 做释放用 if(L==NULL) return; // 结束条件 if(L->data == x){ temp = L; L = L ->next; free(t); del(L,x); }else{ del(L->next,x); } } // 递归统计 int ct = 0; void count(LinkList &L,ElemType x){ if(L == NULL) return; if(L->data == x) ct++; count(L->next,x); }
10) 在带头结点的单链表L中，删除所有值为x的结点，并释放空间，假设值为x的结点不唯一，试编写算法以实现上述操作。
code
++void del_x(linklist &L,int x){ linklist p,temp,pre; p = L->next,pre = L; // pre 防止断链 while(p){ if(p->data == x){ temp = p; p = p->next; pre ->next = p; free(temp); }else{ // 同时后移 pre = p; p = p->next; } } }
11) 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值(头插法建表，遍历)
code
++//法一： 一边遍历一边头插法建立新表 linklist create_head(linklist &L){ liklist newL,p,q; newL = new node(); newL->next = NULL; p = L->next; while(p){ q = new node(); q->data = p->data; q->next = newL->next; newL->next = q; } return newL; } void Visit(linklist L) { linklist p; p=L->next; while(p) { printf("%d ",p->data); p=p->next; } cout<<endl; } 法二： // 采用递归输出 栈的思想 void R_p(linklist L){ if(L->next != NULL){ R_p(L->next); } cout<<L->data<<" "; }
12) 试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点时唯一的）
code
++void delete_MinX(linklist &L){ linklist pre,p,minp,minpre; pre = L; p = L->next;// pre 指向前驱 minp = p,minpre = pre; while(p){ // 遍历寻找最小值 if(p->data <= minp->data){ minp = p; minpre = pre; } pre = p; p = p ->next; } // 删除minp 结点 minpre->next = minp->next; free(minp); }
13) 有一个带头结点的单链表L，设计一个算法使其元素递增有序
code
++// 空间换时间O(n^2) 考的概率不大 void sort(linklist &L){ linklist p,pre,rear; p = L->next; rear = p->next; // rear 保留p后面的链表保证不断链 p->next = NULL; // 让 L 只有一个结点， 重构 L p = rear; // 遍历剩下的内容链表 while(p){ rear = p->next; pre = L; while(pre->next!= NULL && pre->next->data < p->data){ // 在新L中找到p->data应该的位置 pre = pre->next; } p->next = pre->next; // 尾插法 把 p 插入到新L 中 pre -> next = p;// 尾插法 把 p 插入到 新L 中 p = rear; // 继续遍历 旧L 剩下的内容 } }
14) 设在一个带表结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素的元素（若存在）
数字之间，字母之间等问题
code
++void delete_between(linklist &L,ElemType x,ElemType y){ linklist p,pre,temp; p = L->next; pre = L; while(p){ if(p->data >= x && p->data <= y){ // 如果介于之间 // 删除 pre->next = p->next; free(p); p = pre->next; }else{ // 否则继续遍历 pre = p; p = p->next; } } }
掌握解题思想，先走k步，然后一同走，
code
++// 公共结点指， 两个链表从某一结点开始， next都指向同一个节点 Y型 // 长的先走k步,然后一同走,第一个相同的结点即为公共结点初始点 linklist Common(linklist A,linklist B){ linklist pa,pb; int lena = 0 ,lenb = 0,k; pa = A->next; pb = B->next; // 求lena lenb while(pa){ lena++;pa=pa->next; } while(pb){ lenb++;pb=pb->next; } // 长链赋给 pa 断链 赋给 pb if(lena>lenb) { k = lena-lenb; pa = A->next; pb = B->next; }else{ k = lenb-lena; pa = B->next; pb = A->next; } // 先走k步 while(k--) pa = pa->next; // 同时走，第一个相同的结点即为公共链的起点 while(pa){ if( pa->data == pb->data){ return pa; }else { pa = pa->next; pb = pb->next; } } return NULL; }
16) 给定一个带表头结点的单链表，设head为头指针，结点的结构为（data，next），data为整形元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间 (注意)：不允许使用数组作为辅助空间）
code
++// 每次寻找最小的结点输出 O(n^2) // pre记录的是最小值的前驱，pre->next 既为最小值结点 // p 相等于记录的是最小值结点 // 每次比较的是 p->next->data 与 pre->next->data； 即 最小值后一个结点与最小值结点 void fun(linklist &Head){ while(Head->next!=NULL){ linklist pre,p,temp; pre = Head;p = pre->next; // 寻找最小值结点 while(p->next!=NULL){ // pre->next为最小值结点， p->next为最小值结点后继一个结点 if(p->next->data < pre->next->data ){ pre = p; //updata } p = p->next; } cout<<pre->next->data<<endl;//输出最小结点值 // 释放空间，free，并保证不断链 p = pre->next; // pre->next = p->next;//保正不断链 free(p); } free(Head); }
17) 设C={a1,b1,a2,b2…,an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,…,an} B={bn,…,b2,b1}
code
++// 思想： A存放的是奇数位置，尾插法 ； B存放的是偶数位置，头插法 void fun2(linklist &L){ linklist la,lb,pl,pa,pb,temp; la = new node();lb = new node(); la->next = NULL,lb->next = NULL; pa = la;pb = lb; pl = L->next; int i = 0; while(pl){ i++; temp = pl->next; // 保存后继结点，防止断链 if(i%2==1){ // A采用尾插法 pl->next = NULL; // 很重要,保证尾必为null pa->next = pl; pa = pl; }else{ // B采用头插法 pl->next = pb->next; pb->next = pl; } pl = temp; } Visit(la); Visit(lb); }
18) 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如（7,10,10,21,30,42,42,42,51,70）将变作（7,10,21,30,42,51,70）
code
++// 递增有序， 相同的挨着， 一个pre 一个 p 比较p->next是否和pre->next 相同 // 相同删除 p结点 O(N) void delete_same(linklist &L){ linklist pre,p,temp; pre = L;p = pre->next; while(p->next!=NULL){ temp = p->next; // 防止断链 if(p->next->data == pre->next->data){ pre->next = p->next; free(p); }else{ pre = p; } p = temp; } }
19) 设A和B是两个单链表（带头结点），其中元素递增有序，设计一个算法从A和B中公共元素产生单链表C，要求不破坏A B 的结点
code
++//有序 C中元素即是A的也是B的 尾插建链表即可 void fun3(linklist &A,linklist &B){ linklist C,pa,pb,pc,temp; C = new node(); C->next = NULL; pc = C; pa = A->next,pb = B->next; while(pa && pb){ // 小折后移 if( pa->data < pb->data){ pa = pa->next; }else if( pa->data > pb->data){ pb = pb->next; }else { // 相同值 temp = new node(); temp->data = pa->data; pc->next = temp; /* 如果这样写就会出现图2的情况 pc->next = pa; pc = pa; */ pc = temp; // 同时后移 pa = pa->next; pb = pb->next; } } Visit(C); }
20) 已知两个链表A和B分别表示两个集合，其元素递增排列。绘制函数，求A与B的交集，并存放于A链表中。
code
++// 有序， 相同存入，AB同时后移， 不同，小者后移 void fun4(linklist &A,linklist &B){ linklist pa,pb,pre,temp; pa = A->next;pb = B->next; pre = A; // pre 指向A 重构A链表 while(pa&&pb){ // 小者后移 if( pa->data < pb->data){ pa = pa ->next; }else if(pa->data > pb->data){ pb = pb->next; }else{ // 相等时存入， temp = new node(); temp->data = pa->data; pre->next = temp; pre = temp; pa = pa->next; pb = pb->next; } } }
21) 头指针分别为la,lb的带头结点的单链表中，结点按元素递增有序排列，将la和lb两个链表合并成按元素递增有序的单链表，要求不另外开辟空间，la作为合并后的单链表的头结点(951.Y19)
code
++// 归并 原理与上题一致 linklist Union(linklist la,linklist lb){ linklist p,q,r,s; p = la->next,q = lb->next; r = la; // r重构la while( p && q){ if( p->data < q->data){ r->next = p; r = p; p = p->next; }else if( p->data > q->data){ r->next = q; r = q; q = q->next; } else { r->next = p; r = p; p = p->next; s = q->next; free(q); q = s; } if(p) r->next = p; else if(q) r->next = q; } return la; }
22) 两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列
code
++/* * 模式匹配 链表实现 一般算法 O(n^2) * 带头结点, 当相同时，同时后移，， 当不相同时，B从头开始，A后移一个 * 判断条件： 如果B跑完说明匹配完成，否则不存在 */ int Pattern(linklist A,linklist B){ linklist pa,pb,pre; pa = A->next,pb = B->next; pre = A->next; while(pa&&pb){ // 相同，同时后移 if(pa->data == pb->data){ pa = pa->next; pb = pb->next; }else{ // 不相同 A后移 pre = pre->next; pa = pre; // A后移一个结点后从新匹配， pb = B->next; // B从头开始 } } return pb == NULL? 1:0; // 如果pb 跑完说明匹配完成存在 }
23) 设计一个算法用于判断带头结点的循环双链表是否对称
code
++/* * 对称指 设各元素值 a1,a2,...,an, 则有 ai=an-i+1 ， * 即指： a1= an ， a2= an-1 。。。。。。。 * p 从头， q 从尾 当两个相同时，p后移，q前移，一旦不同则break， * 结束条件 p==q |｜p->next = q; */ int flag1(linklist L){ linklist p,q; p = L->next; p = L->prior; int flag = 1; // 初始默认对称 while(p!=q && p->next != q ){ if( p->data == q->data){ p = p->next; q = q->prior; }else { flag = 0; break; } } return flag; }
24) 有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
code
++/** * */ void fun5(linklist &h1,linklist &h2){ linklist p,q; p = h1,q = h2; while(p->next != h1){ p = p->next; } while(q->next != h2){ q = q->next; } p->next = h2; q->next = h1; }
25) 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表为空位置，再删除表头结点
code
++/** * 同第16方法一致，这里为循环电单链表，判空条件需改变 */ void Del_all(linklist &L){ linklist p,pre,minp,minpre; // 没循环一次L减少一个结点，当L->next为L时，说明全部删完 while(L->next! = L){ p = L->next;pre = L; minp = p, minpre = pre; // 找到最小结点 while(p->next != L){ // 循环单链表 // 找到最小结点 if( p->data < minp->data){ minp = p; minpre = pre; }else{ pre = p; p = p->next; } } //free minp cout<<minp->data<<endl; minpre->next = minp->next; // 删除节点保证不断链 free(minp); } free(L); }
26) 已知带头结点单链表，头指针list，不改变链表的前提下设计高效的算法，查找链表中倒数第k个位置上的节点的值(408.Y09)
code
++/** * 掌握思想很重要，O(n)内实现 * 两个指针p,q， p先走k步，然后p,q一起走，当p到时，q即为倒数第k个位置 * 有可能会出现 k 大于表长的情况,需要判断 */ int fun6(linklist list,int k){ linklist p,q; p = list->next; q = list->next; int i = 1; while(p){ // p 走k步 if(i <= k) { i++; } else{ // p,q 同时走 q = q->next; } p = p->next; } // k > n if( i < k){ return 0; } cout<<q->data<<endl; // 此时q->data即为倒数第k个位置 return 1; }
27) 假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,可共享相同的后缀存储空间,例如,“ loading”和" being”的存储映像如下图所示(408,Y12)
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为 data next请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符主所在结点的位置p)。要求
code
++/** * 求公共后缀, 求strlen(str1),strlen(str2); * 求差k， 大者先走k步， 然后同时走，第一个相等的即为公共后缀起点 */ typedef struct link{ char data; link *next; }node,*linklist; linklist Common2(linklist str1,linklist str2){ linklist p,q,s,l; p = str1->next,q = str2->next; int len1 = 0,len2 = 0,k; while(p){ p = p->next,len1++;} // 求str1长度 while(q){ q = q->next,len2++;} // 求str2长度 // 让 s指向短链 ；l指向长链 if(len1 < len2){ k = len2 - len1; s = str1->next; l = str2->next; } else{ k = len1 - len2; s = str2->next; l = str1->next; } while(k--){ // 或者 for(int i = 0 ;i < k ;i++) l = l->next; } while(s&&l){ if( s->data == l->data){ return s; // 返回s的起始位置,此时s->data即为第一个相同元素(不带头结点) /* 此时返回的是带头结点的 linklist temp = new node(); temp->next = s; return temp; */ }else{ s = s->next; l = l->next; } } return new node(); }
28) 用单链表保存m个整数,结点的结构为data,link,|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如下:(408,Y15)
code
++/** * 删除重复结点,无序 * 建立一个map索引,存放data,如果不存在则,链表跳过，否则删除这个结点， * 这里求的是|data| 所以索引用数组即可 * 时间O(m),空间O(n) * */ void fun6(linklist &Head,int n){ linklist p,pre; int vis[n+1]; // 初始化vis 标记为0; memset(vis,0,sizeof(vis)); p = Head->next;pre = Head; while(p){ // 第一次存在，跳过(保留) if(!vis[abs(p->data)]){ vis[abs(p->data)] = 1; pre = p; p = p->next; }else{ //重复 pre->next = p->next; free(p); //释放 p = pre->next; // 删除p后,保证不断链 } } }
