数据结构学习笔记（1）——线性表

忘是亡心i 2022-10-08 05:52 109阅读 0赞

# 线性表的结构体定义与基本操作 #

## 线性表的结构体定义 ##

1.  顺序表的结构体定义

一个顺序表中包含一个存储表中元素的数组data\[\]和一个指示元素个数的变量length：

#define maxSize 100
    typedef struct{
        
    	int data[maxSize]; // 默认int型，可换
    	int legth;
    }Sqlist;

简单写法：

int A[maxSize]
    int n;

1.  单链表的结点定义

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

1.  双链表的结点定义

typedef struct DLNode
    {
        
    	int data;//数据域
    	struct DLNode *prior;//指向前驱结点的指针
    	struct DLNode *next; //指向后继结点的指针
    }DLNode; //定义双链表结点类型

## 顺序表的操作 ##

1.  按元素值的查找算法

// 在顺序表中查找第一个和e值相等的元素，并返回其下标
    int findElem(Sqlist L,int e){
        
    	int i;
    	for(i=0;i<L.length;i++){
        
    		if(e==L.data[i]){
        
    			return i;
    		}
    	}
    	return -1; //查找失败，标记-1
    }

1.  插入数据元素的算法

// 在顺序表L的p（0≤p≤length）位置上插入新元素
    int insert(Sqlist &L,int p,int e){
         //L要发生改变，所以要用引用型
    	int i;
    	if(p<0 || p>L.length || L.length==maxSize ){
         //检查是否越界
    		return 0;
    	}
    	for(i=L.length-1;i>=p;i--){
         //p位置及p以后的所有元素朝后挪
    		L.data[i+1]=L.data[i];
    	}
    	L.data[p]=e; 
    	(L.lenth)++;
    	return 1; 
    }

3.删除数据的算法

// 删除书序表L中下标p(0≤p≤length-1)的元素，并将删除的元素赋值给e
    int deleteElem(Sqlist &L,int p, int &e){
        
    	int i;
    	if（p<0||p>length-1） return 0; //检查参数合法性
    	e=L.data[p]; //被删除元素赋值给e
    	for(i=p;p<=L.length-1;i--){
         //从位置p开始，将后一个数赋值给前一个位置
    		L.data[i]=L.data[i+1];
    	}
    	--(L.length);//L长度-1
    	return 1;
    }

4.初始化

只需要将length设为0即可：

void initList(Sqlist &L){
        
    	L.length=0;
    }

5.求指定位置元素的值

int getElem(Sqlist L，int p,int &e){
        
    	if(p<0||p>L.length-1) return 0;
    	e=L.data[p];
    	return 1;
    }

## 单链表的操作 ##

1.单链表的建立——尾插法

//n个元素存储在数组a中
    void createListR(LNode *&C,int a[],int n){
        
    	LNode *s,*r; 
    	C=(LNode*)malloc(sizeof(LNode)); C->next=NULL; 	//申请C的头结点空间
    	r=C; 											//给r赋初始值；r始终指向C的终端结点
    	for(int i=0;i<n;i++){
        
    		s=(LNode*)malloc(sizeof(LNode));  			//循环申请n个结点
    		s->data=a[i]; 								//从数组中取值赋给s的数据域
    		r->next=s; 									//将s结点接在C的末端
    		r=r->next;						 			//刷新r
    	}	
    	r->next=NULL;
    }

为什么在构造头结点时要给终端结点赋NULL？  
良好的代码习惯，这样可以避免后续操作（很多循环判断条件会用到）时很多因终端结点非NULL而引起的错误。

2.单链表的建立——头插法

void createListF(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指向原链表中的第一个元素，再将头结点的next指向s
    		s->next=C->next;
    		c->next=s;
    	}
    }

思考：以上是带头结点的单链表的头插法与尾插法，考虑一下不带头结点和尾结点的单链表的插入？

3.单链表的归并——尾插法——顺序插入

A、B为带头结点的单链表，其中元素递增有序。设计一个算法，将A和B合并成一个按元素值非递减有序的链表C。

void merge（LNode *A,LNode *B,LNode *&C）{
        
    	
    	// 用p和q来指向链表AB中的最小值，即最前面的值
    	LNode *p=A->next; 
    	LNode *q=B->next;
    	C=A; C->next=NULL; free(B); //将A的头结点赋给C，并释放掉B的头结点（已经将链表B中的首个结点赋给q了）
    	LNode *r = C; //r始终指向C的终端结点
    	//开始归并
    	while(p!=NULL&&q!=NULL){
        
    		if(p->data<=q->data){
         //比较当前p和q的大小，将小的那一个用r接在C后，每接一个刷新指针
    			r->next=p;
    			p=p->next;
    			r=r->next;
    		}else{
        
    			r->next=q;
    			q=q->next;
    			r=r->next;
    		}
    	}
    	// 剩下的全部一次性接在C后
    	if(p!=NULL) r->next=p;
    	if(q!=NULL) r->next=q;
    }

4.单链表的归并——头插法——逆序插入

A、B为带头结点的单链表，其中元素递增有序。设计一个算法，将A和B合并成一个按元素值递减有序的链表C。

void merge（LNode *A,LNode *B,LNode *&C）{
        
    	
    	LNode *p=A->next; 
    	LNode *q=B->next;
    	C=A; C->next=NULL; free(B);
    	LNode *s; //s用来接收新结点	
    	//归并
    	while(p->data<=q->data){
        
    		s=p;
    		//头插
    		s->next=C->next;
    		C->next=s;
    		//刷新指针p
    		p=p->next;
    	}else{
        
    		s=q;
    		s->next=C->next;
    		C->next=s;
    		q=q->next;
    	}
    	//下面是头插法归并和尾插法归并不同的地方，头插法归并剩余的元素需要逐个插入到C中
    	while(p!NULL){
        
    		s=p;
    		s-next=c->next;
    		c-next=s;
    		p=p->next;
    	}
    	while(q!NULL){
        
    		s=q;
    		s-next=c->next;
    		c-next=s;
    		q=q->next;
    	}
    	//可以稍作改进，只需要用s记录下此时指针即可，p和q一定只有一个还有剩余，不可能两个都有剩余。
    	/*
    	s=NULL; //先将s置空
    	if(p!=NULL){s=p;}
    	if(q!=NULL){s=q;}
    	while(s!=NULL){
    		s->next=C->next;
    		C-next=s；
    		s=s->next;
    	}
    	*/
    }

5.单链表中元素的删除与插入

插入操作在上面已经展现：

{
        
    	s->next=p->next;
    	p->next=s;
    }

注意两个语句的顺序不能颠倒。删除操作比较简单：

{
    	p->next=p->next->next;
    }

但完整的删除语法要释放内存，正确的写法是：

{
        
    	q=p->next;
    	p->next=p->next->next;
    	free(q);
    }

可以看到，在单链表中删除某个结点必须要知道它的前驱结点。

6.单链表的查找

如果只是简单的查找，则：

LNode* findLNode(LNode *C,int x){
        
    	LNode *p=C->next;
    	while(p!=NULL){
        
    		if(p->data==x){
        
    			break;
    		}else{
        
    			p=p->next;
    		}
    	}
    	return p;
    }

例题：查找链表C（带头结点）中是否存在一个值为x的元素，如果存在，则删除该结点然后返回1，否则返回0

int findAndDelete(LNode *C,int x){
        		//C的表头结点不会改变，所以这里用引用型，C除了表头结点外其他结点都可以改变
    	LNode *p,*q;
    	p=C;
    	while(p->next!=NULL){
        
    		if(p->next->data==x) break;			//找到x时此时p指向的是x的前一个位置,这是因为要删除结点必须知道它的前一个结点
    		p=p->next;
    	}
    	if(p->next==NULL){
        	//即使是最后一个元素找到了x，p也指向的是倒数第二个元素，此时p->next!=NULL
    		return 0;
    	}else{
        
    		//删除操作
    		q=p->next;
    		p->next=p->next->next;
    		free(q);
    		//删除成功返回1
    		return 1;
    	}
    }

## 双链表的操作 ##

1.尾插法建立双链表

void createDListR(DLNode *&L,int a[],int n){
        
    	DLNode *s,*r;
    	//create head node
    	L=(DLNode*)malloc(sizeof(DLNode));
    	L->prior=NULL;
    	L->next=NULL;
    	r=L;
    	for(int i=0;i<n;i++){
        
    		s=(DLNode*)malloc(sizeof(DLNode));
    		s->data=a[i];
    		//到这里和单链表几乎没有区别，插入时也只是多了一步前驱结点的定义过程。
    		r->next=s;
    		s->prior=r;
    		r=s; //r=r->next;
    	}
    	r->next=NULL;
    }

2.双链表——查找结点

单链表和双链表的查找算法没有任何区别：

DLNode* findDNode(DLNode *C,int x){
        
    	DLNode *p=C->next;
    	while(p!=NULL){
        
    		if(p->data==x){
        
    			break;
    		}else{
        
    			p=p->next;
    		}
    	}
    	return p;
    }

如果找到，则返回结点地址p，如果没找到，循环因p=NULL而结束，返回p;

3.双链表——插入结点

在双链表中p所指的结点后插入一个新结点s:

{
        
    	s->next=p->next;
    	s->prior=p;
    	p->next=s;
    	s->next->prior=s;
    }

关键是先后顺序，要先将插入的结点的前后接好，这样才不会发生链断后找不到结点的情况。

4.双链表——删除结点

删除p的后继结点：

{
        
    	q=p->next;
    	p->next=q->next;
    	p->next->prior=p;
    	free(q);
    }

## 逆置问题 ##

算法：给定一个线性表，如何将其中的元素逆置？可设置两个指针，分别指向表头和表尾，边交换元素边向中间挪动，直到两个指针相遇。

//假如元素存在数组a[]中，left和right是数组两端元素的下标。
    {
        
    	for(int i=left，j=right;i<j;i++,j--){
         //注意，这里的循环条件不能写成i!=j，如果数组中的元素有偶数个，会发生i和j相互跨过对方，循环不会结束。
    		temp = a[i];
    		a[i] = a[j];
    		a[j] = temp;
    	}
    }

逆置相当于把原来数组中元素逆序重新放在数组里。

例题：

> （1）将数组的前k（k<n）个元素逆序后移动到数组后端，原数组数据不丢失，其余元素的位置无关紧要；  
> 答：将整个数组逆置即可。

> （2）将数组的前k（k<n）个元素保持原顺序移动到数组后端，原数组数据不丢失，其余元素的位置无关紧要；  
> 答：将前k个元素逆置后将整个数组逆置。

> （3）将数组中的前n个元素（x0,x1,x2,…,xn-1）经过移动后变为（xp,xp+1,…,xn-1,x0,x1,…,xp-1）,即循环左移p(0<p<n)  
> 答：观察移动后的元素位置，相当于把前p个元素顺序不变放在后端，后n-p个元素顺序不变放在前端。所以先将前p个元素和后n-p个元素分别逆置，再将整个数组逆置。

## 课后题 ##

二、综合应用题

1.基础题

（4）设计一个算法，从一给定的顺序表L中删除下标i~j(i<=j包括i和j的所有元素),假设i和j都是合法的。

int deleteElems(Sqlist &L,int i,int j){
        
    	//从i开始，用后面的元素覆盖掉要删除的元素
    	for(int k=j+1;k<L.length;k++){
        	
    		L.data[i]=L.data[k];
    		i++;
    	}
    }

（5）有一个顺序表L,其元素为整型数据，设计一个算法，将L中所有小于表头元素的整数放在前半部分，大于表头元素的整数放在后半部分。

void move(Sqlist &L){
        
    	int i=0;
    	int j=L.length-1;
    	int temp=L.data[i]; //用temp来保存表头元素的值
    	while(i<j){
        
    		while(i<j&&L.data[j]>temp) --j; //j从最右边往左扫描，找到比temp小的数时跳出while执行if
    		
    		if(i<j){
         						//为什么在这里还要再判断一次i<j呢？经过上一步，j有可能已经小于等于i了。
    			L.data[i]=L.data[j];        //将大的数放在位置i上，i向右挪
    			++i;
    		}
    		
    		while(i<j&&L.data[i]<temp) ++i;	//i从左往右扫描，找到比temp大的数时跳出while执行if
    			
    		if(i<j){
        
    			L.data[j]=L.data[i];		//将找到的这个大于temp的数放在给j位置上，j往左挪
    			--j;						
    		}
    	}
    	L.data[i]=temp;
    }
    	/*经过一次循环，j从右往左扫，将一个大的数放在了前半部分，i从左往右扫，将一个小的数放在了后半部分。
    	每次元素覆盖时，之前位置上的数已经放在了前半部分/后半部分，而temp值始终保存着最开始a[0]，所以不用担心数据丢失。
    	当i==j时循环结束，最后一次循环结束时i和j所指的数是也是循环内最后一次发生覆盖元素的数，
    	它的值已经保存在了别的位置上，此时将temp放在这里，所有数据保存完整。*/

（6）有一个递增非空单链表，设计一个算法删除值域重复的结点。例如，\{1,1, 2, 3, 3, 3, 4, 4,7, 7, 7, 9, 9, 9\}经过删除后变成\{1,2, 3, 4, 7, 9\}。

void deleteRepeat1(LNode *L){
         		//表头结点不用改变，这里传指针型即可
    	LNode *p=L->next;			 	//p指向首个结点
    	LNode *q;
    	while(p->next!=NULL){
        
    		if(p->data==p->next->data){
        	//由于链表递增，所以重复的元素一定是相连的，如果p的值和下一个结点的值相等，就删除它
    			q=p->next;
    			p->next=p->next->next;
    			free(q);
    		}else{
        
    			p=p->next;				//如果不相等，p向右移
    		}
    	}
    }

（7）设计一个算法删除单链表L(有头结点）中的一个最小值结点。

void  deleteMin(LNode *L){
        
    	LNode *q;
    	LNode *p=L->next;
    	LNode *minPrior=L; //假设第一个结点是最小的，min始终指向最小结点的前一个结点（方便删除min）
    	while(p->next!=NULL){
        
    		if(p->next->data < p->data){
        
    			minPrior=p;
    		}
    		p=p->next;
    	}
    	q=minPrior->next;
    	minPrior->next=q->next;
    	free(q);
    }

（8）有一个线性表，采用带头结点的单链表L来存储。设计一个算法将其逆置。要求不能建立新结点，只能通过表中已有结点的重新组合来完成。

//链表逆置问题，可以看成是链表的逆序问题，将L看成一个空链表，将结点使用头插法挨个插入即可。

void reverse(LNode *L){
        
    	//将链表从头结点处分开成两部分
    	LNode *p=L->next;
    	L->next=NULL;
    	//temp用来临时记录插入前p的位置
    	LNode *temp;
    	while(p!=NULL){
        
    		temp=p;
    		//头插法
    		p->next=L->next;
    		L->next=p;
    		//刷新p
    		p=temp->next;
    	}	
    }

（9）设计一个算法，将一个头结点为A的单链表（其数据域为整数）分解成两个单链表A和B，使得A链表只含有原来链表中data域为奇数的结点，而B链表只含有原链表中data域为偶数的结点，且保持原来的相对顺序。

//方法一：把AB看成两个空的链表，把每个结点单独取出来判断其值，分类重新按照尾插法插入到A和B中
    void divorce_1(LNode *A,LNode *&B){
        
    	//申请B链表的头结点
    	B=(LNode*)malloc(sizeof(LNode)); 
    	B->next=NULL;
    	// 只保留A的头结点,用p记录其他结点
    	LNode *p=A->next;
    	A->next=NULL; 
    	//现在有两个新的空链表，接下来把结点分类按尾插法插入
    	LNode *temp,*tempA=A,*tempB=B; //tempA、tempB始终指向A/B的终端结点
    	
    	while(p!=NULL){
        
    		//取出结点p
    		temp=p;
    		p->next=NULL;
    		//判断
    		if(p->data%2==0){
        	//偶数,尾插法接入B中	
    			*tempB->next=p;
    		}else{
        				//奇数，尾插法插入A中
    			*tempA->next=p;
    		}
    		p=temp->next;
    	}
    }

//方法二：从A中删除偶数结点，并将其取出来插入到B中
    //注意删除操作时必须要知道前驱结点，这里的删除不用释放空间，结点并不是真正意义上的删除，只是转移到了B中
    void divorce_2(LNode *A,LNode *&B){
        
    	B=(LNode*)malloc(sizeof(LNode)); //申请B链表的头结点
    	B->next=NULL;
    	LNode *p=A;	//p表示偶数结点的前驱结点(删除操作用)
    	LNode *r=B;	//r始终指向B的终端结点
    	LNode *temp;
    	while(p->next!=NULL){
        
    		if(p->next->data % 2 == 0 ){
        
    			//取出偶数结点
    			temp=p->next;
    			p->next=temp->next;
    			temp->next=NULL;
    			//尾插法插在B中
    			r->next=temp;
    			r=r->next;
    		}
    	}
    }

2.思考题

（1）有N个个位正整数存放在int型数组A\[O,…, N-1\]中，N为已定义的常量且N<=9,数组A\[\]的长度为N,另给一个int型变量i,要求只用上述变量(A\[O\]A,…\_\_\_,\[N-1\]与i,这N+l个整型变量）写一个算法，找出这N个整数中的最小者，并且要求不能破坏数组A\[\]中的数据。

> 分析：在数组（顺序表）中查找最小值，需要一个循环变量i来控制循环，一个临时变量记录min。题目中要求只能用到i一个变量，可以让i的十位上的数字作为循环变量，各位上的数作为临时变量。  
> // i%10 取个位数 临时变量  
> // i/10 取十位数 循环变量

int findMin(int a[],int &i){
        
    	i=a[0];						// i赋初始值为a[0]，此时i是个位数，i/10==0，i%10==a[0]
    	while(i/10<=N-1){
        			// i/10 从0开始，递增到N-1
    		
    		if(i%10>a[i/10]){
        
    			i = i - i%10;		//去掉个位数
    			i = i + a[i/10];  	//个位数替换成较小的数组元素值
    		} 
    		i = i+10; 				//十位数增+1（循环变量+1）
    	}
    	return i%10;	//返回个位数即为最小值
    }

（2）写一个函数，逆序打印单链表中的数据，假设指针L指向了单链表的开始结点。

> 分析：采用递归的方法解决

void reprint(LNode *L){
        
    	if(L->next!=NULL){
        
    		reprint(L->next);
    		cout<<L->data<<" ";
    	}
    }

（3）（2021）试编写一个函数，以不多于3n/2的平均比较次数，在一个有n个整数的顺序表A中找出最大值和最小值。

void findMaxAndMin(int A[],int n,int &max,int &min){
        
    	max = min = A[0];
    	for(int i = 1;i<=n-1;){
        
    		/*
    			对于min和max来说，A[i]有三种情况：
    			1.A[i]<min	更新最小值
    			2.A[i]>max	更新最大值
    			3.min<=A[i]<=max	A[i]既不可能是最大值也不可能是最小值，不操作
    		*/
    		if(A[i]>max){
        
    			max = A[i];
    			break; 		
    		}else if(A[i]<min){
        
    			min = A[i];
    		}
    	}
    }

最好情况：当表中的n个整数按从小到大排列时，比较次数为n-1;  
最差情况：当表中的n个整数按从大到小排列时，比较次数为2(n-1);  
每个结点的数值上面说了有三种情况，概率为1/3，每个节点比较1次和比较2次的概率相等，则单个结点的平均比较次数为3/2；  
平均比较次数：（3/2）\*（n-1）=3n/2-3/2

（3）（2022）设有两个用有序链表表示的集合A和B,设计一个算法，判断它们是否相等。

int isEqual(LNode *A,LNode *B){
        
    	LNode *p =A->next;
    	LNode *q =B->next;
    	while(p!=NULL && q!=NULL){
        
    		if(p->data == q->data){
        
    			p=p->next;
    			q=q->next;
    		}else{
        
    			return 0;
    		}
    	}
    	if(p==NULL && q==NULL){
        
    		return 1;
    	}else{
        
    		return 0;
    	}
    }

二、真题精选

（二）综合应用题

1.  已知一个带有表头结点的单链表，结点结构为:

假设该链表只给出了头指针head。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k(k为正整数)个位置上的结点。若查找成功，算法输出该结点的data值，并返回1; 否则，只返回0。要求：  
(1) 描述算法的基本设计思想。  
(2) 描述算法的详细实现步骤。  
(3) 根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++语言实现），关键之处请给出简要注释。

解：(1)基本思想：
    遍历链表，用两个指针p，q，p指向当前结点，q指向当前结点的前k-1个结点，当p指向最后一个结点时，q指向倒数第k个结点。
    
    (2)详细实现步骤：
    	指针p:当前结点；初始值为head->next(指向头结点)
    	指针q:p的前k-1个结点；初始值为head->next(指向头结点)
    	用 i 表示 p 和 q 之间的结点数，初始值为1(中间只有一个头结点)，p 从左到右遍历：
    			当i<=k时，p向右移，q不动；
    			当i>k时，p向右移，q也向右移，直到p指向终端结点时跳出循环，q所指的指针即为链表中倒数第k(k为正整数）个位置上的结点。

int find(LNode *head,int k){
        
    	LNode *p,*q=head->next;
    	int i=1;
    	while(p->next!=NULL){
        
    		p=p->next;
    		i++;
    		if(i>k){
        
    			q=q->next;
    		}
    	}
    }

1.  已知一个整数序列A = (A0, A1, …, A(n-1)), 其中0<=ai<=n (0<=i<n)。若存在ap1 = ap2=…= apm= x且m>n/2(0<=pk<n, 1<=k<=m), 则称x为A的主元素。例如，A= (0, 5, 5, 3, 5, 7, 5, 5), 则5为主元素；又如，A= (0, 5, 5, 3, 5, 1, 5, 7), 则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：  
    (1) 给出算法的基本设计思想。  
    (2) 根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。  
    (3) 说明你所设计算法的时间复杂度和空间复杂度

方法一：排序取中位数；

方法二：抵消法：删除数组中两个不同的数，直到剩下的数都一样。此时剩下的数就是主元素。  
原理：主元素的个数一定是比其他元素的个数至少多1的，任意删去两个不同的数之后，在剩余子数组中，主元素依旧是主元素。随着遍历，最后剩下的数，一定是主元素（因为最多删除n/2-1次）。

计数器：count 初始值为1  
候选值：num 初始值为a\[0\]

遍历数组，  
如果a\[i\]和num值相等，则count+1;  
如果a\[i\]和num值不相等，则count-1;直到count等于0（这意味着随机删除了多组两两不同的数），更换候选值num=a\[i\]，计数器重置为1，从a\[i\]开始接着朝后遍历，直到扫描完整个数组;

如果数组中一定存在主元素，那么最后剩下的值就一定是主元素。可是现在由于数组中不一定存在主元素，最后num的值不一定是主元素，所以遍历结束后我们需要对num进行再次确认。

int majority(int a[],int n){
        
    	int num = a[0];
    	count=1;
    	for(int i=1;i<n;i++){
        
    		if(a[i]==num){
        
    			count++;
    		}else{
        
    			//不相等时需要判断count是否为0
    			if(count>0){
        
    				count--;
    				// count为0，说明前面已经删去了多组两两不相等的数，此时重置候选值和计数器
    			}else{
        
    				num=a[i];
    				count=1;
    			}
    		}		
    	}
    	//遍历结束后，要对num值是否满足条件再进行判断，因为数组a中不一定含有主元素
    	if(count>0){
        
    		count=0;
    		for(int i=0;i<n;i++){
        
    			if(a[i]==num){
        
    				count++;
    			}
    		}
    	}
    	if(count>n/2){
        
    		return num;
    	}else{
        
    		return -1;
    	}
    }
    
    算法的时间复杂度：O(n)
    算法的空间复杂度：O(1)