数据结构学习——线性表的结构体定义和基本操作

深藏阁楼爱情的钟 2022-03-07 00:16 420阅读 0赞

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

#define maxSize 100 //定义一个整型常量maxSize,值为100

### 1.顺序表的结构体定义 ###

typedef struct
    { 
    	int data[maxSize];
    	int length;
    }Sqlist;

也可以这么定义,简洁:

int A[maxSize];
    int n;

### 2.单链表结点定义 ###

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

### 3.双链表结点定义 ###

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

### 4.为结点分配和释放内存 ###

LNode *A = (LNode *)malloc(sizeof(LNode));
    free(A);

## 顺序表的操作 ##

### 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，作为失败标记
    }

### 2.插入数据元素的算法 ###

在顺序表L的第p(0<=p<=length)个位置上插入新的元素e。如果p的输入不正确，则返回0，代表插入失败；如果p的输入正确，则顺序表第p个元素及以后元素右移一个位置，腾出一个空位置插入新元素，顺序表长度增加1，插入操作成功，返回1.  
插入操作代码如下:

int insertElem(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)
    		L.data[i+1]=L.data[i]; //从后往前，逐个将元素往后移动一个位置
    	L.data[p]=e;
    	++(L.length); //表内元素多了一个，因此表长自增1
    	return 1;     //插入成功，返回1
    	
    }

### 3.删除顺序表L中下标为p的元素，成功返回1，否则返回0，并将删除元素的值赋给e。 ###

int deleteElem(Sqlist &L,int p,int &e)
    { 
    	int i;
    	if(p<0||p>L.length-1)
    		return 0;              //位置不对返回0，代表删除不成功
    	e = L.data[p];            //将被删除元素赋值给e
    	for(i=p;i<L.length-1;i++) //从p位置开始，将其后边的元素逐个前移一个位数
    		L.data[i] = L.data[i+1];
    	--(L.length);             //表长减1
    	return 1;                 //删除成功，返回1
    }

## 单链表的操作 ##

例题:A和B是两个单链表(带表头结点)，其中元素递增有序。设计一个算法，将A和B归并成一个按元素值非递减有序的链表C,C由A和B中的结点组成。

### 尾插法(按正序插入) ###

void merge(LNode *A,LNode *B,LNode *&C)
    { 
    	LNode *p = A->next; //p来跟踪A的最小值结点
    	LNode *q = B->next; //q来跟踪B的最小值结点
    	LNode *r; //r始终指向C的终端结点
    	C = A;    //把A的头结点作为C的头结点
    	C->next = NULL;
    	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;
    		}
    	}
    	r->next=NULL;  //这句话可以不加，因为下面两句比会执行其中一句
    	if(p!=NULL) r->next = p; //如果p有剩余，直接将r下一个结点指向p
    	if(q!=NULL) r->next = q; //如果q有剩余，直接将r下一个集结点指向q
    }

### 尾插法建立单链表 ###

void merge(LNode *&C,int a[],int n)
    { 
    	LNode *s,*r; //s用来指向新申请的结点，r始终指向C的终端节点
    	int i;
    	C = (LNode *)malloc(sizeof(LNode)); //申请C的头结点空间
    	C->next = NULL;
    	r = C;
    	for(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; //链表建立完成，C的终端结点的指针域为NULL
    }

### 头插法建立单链表 ###

void merge(LNode *&C,int a[],int n)
    { 
    	LNode *s;
    	int i;
    	C=(LNode *)malloc(sizeof(LNode));
    	C->next = NULL;
    	for(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和B两个链表按递减顺序合并到C链表 ###

void merge(LNode *A,LNode *B,LNode *&C)
    { 
    	LNode *p = A->next;
    	LNode *q = B->next;
    	LNode *s;
    	C=A;
    	C->next=NULL;
    	free(B);
    	while(p!=NULL&&q!=NULL)
    	{ 
    		if(p->data<=q->data)
    		{ 
    			s = p;
    			p = p->next;
    			s->next = C->next;
    			C->next = s;
    		}
    		else
    		{ 
    			s = q;
    			p = q->next;
    			s->next = C->next;
    			C->next = s;
    		}
    	}
    	//这区别于尾插法
    	while(p!=NULL)
    	{ 
    		s = p;
    		p = p->next;
    		s->next = C->next;
    		C->next = s;
    	}
    	while(q!=NULL)
    	{ 
    		s = q;
    		q = q->next;
    		s->next = C->next;
    		C->next = s;
    	}
    }

*  头插法关键语句

s->next = C->next;
    C->next = s;

### 删除结点 ###

假设p为指向a的指针，则只需将p的指针域next指向原来p的下一个结点的下一个结点即可，即:

p->next=p->next->next;

完整的删除操作是:

q=p->next;
    p->next = p->next->next;
    free(q); //调用函数free()来释放q所指结点的内存空间

### 例题 ###

查找链表C(带头结点)中是否存在一个值为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 = q->next;
    		free(q);
    		return 1;
    	}
    }

删除结点要找到要删除结点的前驱结点，而不是直接指向所要删除结点本身。

## 双链表的操作 ##

### 采用尾插法建立双链表 ###

void createDlistR(DLNode *&L,int a[],int n)
    { 
    	DLNode *s,*r;
    	int i;
    	L=(DLNode *)malloc(sizeof(DLNode));
    	L->prior = NULL; //前指针
    	L->next = NULL;  //后指针
    	r = L; //和单链表一样，r始终指向终端结点，开始头结点也是尾结点
    	for(i=0;i<n;i++)
    	{ 
    		s = (DLNode *)malloc(sizeof(DLNode)); //创建新结点
    		s->data = a[i];
    		r->next = s;
    		s->prior = r;
    		r = s;
    	}
    	r->next = 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所指的结点之后插入一个结点s，其操作语句如下:

s->next = p->next;
    s->prior = p;
    p->next = s;
    p->next->prior = s; //假如p指向最后一个结点，则本行去掉

### 删除结点的算法 ###

设要删除双链表中p结点的后继结点，其操作语句如下:

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