本文共 4971 字，大约阅读时间需要 16 分钟。

一、线性表的定义

线性表：零个或多个数据元素的有限序列

1. 元素之间是有顺序的。
2. 第一个元素无前驱，最后一个元素无后驱，其他的每一个元素有且只有一个前驱和后驱。
3. 线性表元素的个数n定义为线性表的长度，n=0，空表。

二、线性表的抽象数据类型

线性表的抽象数据类型定义如下：

/****抽象数据类型定义******/InitList(*L);       //初始化操作，建立一个空的线性表LListEmpty(L);       //若线性表为空，返回true,否则返回falseClearList(*L);      //将线性表清空GetElem(L,i,*e);    //将线性表L中的第i个元素值返回给eLocateElem(L,e);    //查找成功放回序号，查找失败返回0ListInsert(*L,i,e)  //在线性表L的第i个位置插入eListDelet(*L,i,*e)  //删除第i个位置元素，并用e返回其值ListLength(L);      //返回线性表的元素个数

三、线性表的顺序存储结构

1.顺序存储定义：用一段地址连续的存储单元依次存储线性表的数据元素。

/*********顺序存储的结构代码**********/#define MAXSIZE 20    //存储空间初始分配量typedef int ElemType;typedef struct{	ElemType data[MAXSIZE];	int length; } SqList;

顺序存储结构需要三个属性：

• 存储空间的起始位置：数组data
• 线性表的最大存储容量：数组长度MAXSIZE
• 线性表的当前长度：length3.

3.数据长度与线性表长度

• 数据长度：存储的空间长度（MAXSIZE）
• 线性表长度：元素个数（length）

4.地址的计算办法

四、顺序存储结构的插入与删除

1. 获得元素操作
2. 插入操作
3. 删除操作

/**********获得元素的操作******************/ #define OK 1 #define ERROR 0 Statues GetElem(SqList L, int i, ElemType *e) { 	if(L.length==0||i<1||i>L.length)	 return ERROR;	*e=L.data[i-1];	return OK;		}

/***************顺序存储结构的插入**********************/Status ListInsert（SqList *L,int i,ElemType）{	int k;	if(L->length>MAXSIZE)      //线性表已满 		return ERROR;	if( i<1 || i>L->length )   //i的位置不对		return ERROR;	if( i <= L->length)	｛		for(k=L->length-1; k>=i-1; k--)   //将插入位置后的元素向后移动一位		｛			L->data[k+1] = L->data[k];		｝		｝ 	L->data[i-1]=e;	L->length++; }

/******************顺序存储结构的删除*************/ Status ListDelete(SqList *L,int i, ElemType) { 	int k; 	if(L->length==0)     //线性表为空	 	return ERROR；	if( i<1 || i>L->length )   //i的位置不对		return ERROR; 	*e = L->data[i-1] 	if( i <= L->length)	｛		for(k=i; k
   
    length; k--)   //将插入位置后的元素向后移动一位		｛			L->data[k-1] = L->data[k];		｝		｝ 	return OK;  }
   

五、线性表的链式存储结构

1. 顺序存储结构的不足：插入和删除时需要移动大量的元素
2. 线性表的链式存储结构的定义
   结点：
   链表：n个结点链结成一个链表
   单链表：链表中的每个结点只包含一个指针域
   头指针：链表中的第一个结点的存储位置
   头结点：在单链表的第一个结点前附设一个结点，称为头结点
3. 头指针和头结点的异同
   头指针：指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针。头指针是链表的必要的元素
   头结点：放在第一个元素之前的结点，头结点不是链表的必须要素
4. 线性表链式存储结构代码描述

/***************线性表的单链表存储结构*****************/typedef struct Node{	ElemType data;	struct Node *next; } Node; typedef struct Node *LinkList;

链接由结点构成

六、单链表的读取

获取单链表的第i个数据

1. 声明一个指针p指向单链表的第一给结点 j=1;
2. j<i时，遍历链表，让p指针向后移动，不断的指向下一个结点，j++;
3. 若到单链表的尾部，则说明i 点不存在；
4. 否则查找成功，返回结点p的数据、

Status GetElem(LinkList L,int i,ElemType *e) { 	int j; 	LinkList p;     //声明一个指针p	p = L->next;    //p指向链表L的第一个结点 	j = 1;	while( p && jnext;		j++;	 }	if(!p || j>i)	 	return -1;		 	*e = p->data;	return 0;  }

七、单链表的插入与删除

1. 单链表的插入
   先把p的后继结点改成s的后继结点
   在把s变成p的后继结点
   （顺序不可以变）

/**********************单链表的插入（单链表第i个数据插入结点）*************************/ /* 	 1.声明一指针p指向链表的头结点，同时 j = 1 	 2.当 j < i 时，遍历链表，让p指针向后移动，不断指向下一个结点， p++	 3.若到链表的末尾p为空，则说明第i个结点不存在	 4.否则查找成功，在系统中生成一个空节点s	 5.将元素e赋值给s->data	 6.单链表的插入标准语句 s->next = p->next       p->next = s	 7.返回成功*/Status ListInsert(LinkList *L,int i,ElemType e) {	int j;	LinkList p,s;	p = *L;     //指针指向链表l 	j = 1;	while( p && j < i )	{		p = p->next;		j++;	}	if(!P || j < i)		return -1;	s = (LinkList)malloc(sizeof(Node)) ;     //生成新结点 	s->data = e;	s->next = p->next;	p->next = s;	return 0;	}

2. 单链表的删除
   只需要一步：p->next = p->next->next

/******************单链表的删除***************//*		1.声明一个指针p指向链表头指针， j = 1	2.当 i < j时，就遍历链表，让p指针向后移动，不断的指向下一个结点， j++	3.若到链表尾部p为空，则说明i结点不存在	4.否则查找成功，将欲删除的结点 p->next赋值给q	5.单链表的删除标准语句 p->next = q->next	6.将q结点中的数据赋值给e，作为返回	7.释放q结点	8.返回成功*/Status ListDelete(LinkList *L,int i,ElemType e){	int j;	LinkList p,q;	j = 1;	while(p->next && j < i)	{		p = p->next;		j++;	 } 	 if( !(p->next) || j > i )	 	return -1;	 		q = p->next;	p->next = q->next;	*e = q->data;	free(q);    //释放结点q	return 0; }

八、单链表整表的建立

单链表的建立就是一个动态生成链表的过程；从‘空表‘的初始状态起，依次建立各元素结点，并逐个插入链表。

/*********单链表整表创建的算法：头插法********************//*	1.声明一个 指针p 和 计数变量 i;	2.初始化一个空链表L；	3.让L的头结点的指针指向空，即建立一个带头结点的单链表； 	4.循环：		生产一个新节点赋值给p; 		生成一个新节点赋值给p的数据域 p->data;		将p插入到头结点与前一个新结点之间；		*/void CreatListHead(LinkList *L,int n){	LinkList p;      //声明指针 p	int i;	srand(time(0));	*L = (LinkList)malloc(sizeof(Node));  	(*L)->next = NULL;           //创建一个带头结点的链表L		for( i = 0; i < n; i++)	{		p = (LinkList) malloc (sizeof(Node));   //生成新结点		p->data = rand()%100 + 1;		p->next = (*L)->next;   //查入到表头 	 } 	}/*********单链表整表创建的算法：尾插法********************/void CreatListTail(LinkList *L,int n){	LinkList p,r;;	int i;	srand(time(0));	*L = (LinkList)malloc(sizeof(Node));   //为整个线性表	r = L;	for( i = 0; i < n; i++)	{		p = (Node *)malloc(sizeof(Node));    //生成新结点		p->data = rand()%100+1;		r->next = p;    //将表尾终端结点的指针指向新结点 		r = p;          //新结点变成尾结点 	 } 	 r->next = NULL;    //表示当前链表结束  }

九、单链表整表的删除

/*********************单链表的删除 ************************//*	1.声明一个结点p和q;	2.将第一个结点赋值给p;	3.循环：		将下一个结点赋值给q;		释放p;		将q赋值给p;*/Status ClearList(LinkList *L){	LinkList p,q;	p = (*L)->next;    //p指向第一个结点	while(p)           //没到表尾 	{		q = p->next;		free(q);		p = q;	 } 	 (*L)->next =NULL;	 return 0; }

十、静态链表

1. 定义：用数组描述的链表叫做静态链表
2. 数组元素都是由两个数据域组成的，data和cur.
   data:用来存放数据元素
   cur:相当于单链表中的next，存放元素的后继在数组中的下标，称作游标

转载地址：https://blog.csdn.net/weixin_43486985/article/details/96364836 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！