线性表代码总结

快来打我* 2023-06-11 14:28 14阅读 0赞

### 文章目录 ###

*   *   *   *  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;
    }

1.  将一个带头结点的单链表，使其元素递增有序

/** 直接插入排序，构成只含有一个数据结点的有序单链表，然后依次扫描单链表中剩余结点*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; 
    }