线性表（顺序表、单链表、双链表、循环表）_顺序表的按照值查找序号操作程序流程图

目录

自己敲的时候出现的问题

顺序表

顺序表的分配

顺序表的初始化（静态动态）

动态分配+增加长度：

插入操作✅（动态的也一样）

 删除操作✅

按值查找和按位查找 ✅

单链表

定义结点及各名词的解释

增加一个新结点：

初始化单链表

头插法建立单链表

尾插法建立单链表

按序号查找结点值

插入结点（p从头开始遍历时）

删除结点

双链表 

循环单、双链表

静态链表​​​​​​​

---

自己敲的时候出现的问题

1、sequence:顺序、按顺序。

初始化顺序表的函数名：InitList,形参：（Sqlist *L）

插入操作时，形参不仅只有SeqList *L,ElemType e,还应该有int i，这个不要在函数内部定义。

2、在插入函数里，没有判断i>Maxsize的情况，忘了下标是0-(n-1)。

3、删除操作看准：要删除的元素e已知

插入和删除的函数类型都是bool。

提前令 *e  = L -> data[i-1];

顺序表

顺序表的分配

typedef int ElemType;
//静态分配
#define MaxSize 10 //定义最大长度
typedef struct 
{	int data[MaxSize];//用静态的“数组”存放数据元素
	int length;				//顺序表的当前长度
}SqList;					//顺序表的类型定义（静态分配方式）
 
//动态分配
#define InitSize 10			//定义顺序表的初始长度
typedef struct{
    ElemType *data;			//指示动态分配数组的指针
	int MaxSize;			//顺序表的最大容量
	int length;				//顺序表的当前长度
}SeqList;					//顺序表的类型定义（动态分配)

C语言里，动态内存申请：

C语言里初始动态分配语句为：

L.data = (Elemtype*)malloc(sizeof(Elemtype)*InitSize);

在上面的动态分配中：data是动态分配出的数组的名字，length代表当前已经分配的长度，MaxSize代表最多分配的长度，等于或超过这个长度就要扩容。 

顺序表的初始化（静态动态）

//初始化静态分配的顺序表。初始化的过程：将元素值、表长都初始化为0。
void InitList(SqList *L)
{
    for (int i = 0; i < MaxSize; i++)
    {
        L->data[i] = 0;
    }
    L->length = 0;   
}
 
//顺序表的初始化——动态分配
void InitList(SeqList *L)
{
	L->data = (int *)malloc(InitSize * sizeof(int));
	L->length = 0;
	L-> MaxSize = InitSize;
}

动态分配+增加长度：

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10 //定义最大长度
 
//要想使用malloc函数和free函数时，必须有stdlib.h头文件。
 
typedef struct 
{
	int *data;//注意看，这里是指针域
	int MaxSize;
	int length;
}SeqList;
 
//每个数据元素分配空间大小 MaxSize* sizeof(ElemType);
 
//顺序表的初始化——动态分配
void InitList(SeqList *L)
{
	L->data = (int *)malloc(InitSize * sizeof(int));
	L->length = 0;
	L-> MaxSize = InitSize;
}
 
//增加动态数组的长度
void IncreaseSize(SeqList *L,int len)
{
	int *p = L->data;//p指针指向原来的地方，接下来，data会指向另一个空间，免得找不到。
	L->data = (int *) malloc((L->MaxSize+len)*sizeof(int));//重新在别的地方动态分配一片更大的空间。
	for (int i = 0; i < L->length; i++)
	{
		L->data[i] = p[i];//将原来的数据复制到新区域
	}
	L->MaxSize = L->MaxSize+len;//顺序表最大长度增加len
	free(p);	//释放原来的内存空间，系统自动回收。
}
 
int main()
{
	SeqList L;	//声明一个顺序表
	InitList(&L);//初始化顺序表
 
    //…省略一些代码，如：向表中填满。
	IncreaseSize(&L,5);
	return 0;
}

插入操作✅（动态的也一样）

//顺序表的基本操作——插入和删除
#include <stdio.h>
#include <stdbool.h>
#define MaxSize 10 //定义最大长度
 
typedef  int ElemType;
//采用静态分配
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;
 
void InitList(SqList *L)
{
	for (int i = 0; i < MaxSize; i++)
	{
		(*L).data[i] = 0;//将所有数据元素设置为默认初始值
	}
	(*L).length = 0;		//顺序表初始长度为0	
}
 
//将e插入data[i]处。
void ListInsert(SqList *L,int i,int e)
{
	for (int j = L->length; j >= i; j--)
	{
		//将第i个元素及之后的元素后移
		L->data[j] =L->data[j-1];
	}
	L->data[i-1] = e;
	//插入e,题目中会说将e插在i处，是插在数组下标为i-1处。
	L->length ++;	 //长度加1
}
 
//改进一下，解决问题：是否越界等
bool ListInsert1(SqList *L, int i, int e){
	if (i < 1 || i > L->length + 1)
	{
		return false;
		//判断值范围是否有效
	}
	if (L->length >= MaxSize)
	{
		//当前存储空间已满，不能插入
		return false;
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j-1];
	}
	L->data[i-1] = e;
	L->length ++;
	return true;
}
 
int main()
{
	SqList L;//声明结构体变量L.
	InitList(&L);//初始化
	//将数据填入顺序表的过程省略
	//ListInsert(&L,3,3);//插入
	ListInsert1(&L,3,3);//改进版
	return 0;
}

 删除操作✅

bool ListDelete(SqList *L, int i, int *e)
{
	if (i < 1 || i > L->length)
	{
		return false;
	}
	*e  = L->data[i-1];//选择删除数组下标为i-1的值赋给e
	for (int j= i; j < L->length; j++)
	{
		//删除后，后面的元素依次前移
		L->data[j-1] = L->data[j];
	}
	L->length --;
	return true;
}
 
int main()
{
	SqList L;
	int e = -1;
	if (ListDelete(&L,3,&e))
	{
		printf("已经删除第3个元素,删除元素值为%d\n",e);
	}
	else{
		printf("位序不合法，删除失败\n");
	}
	return 0;
}

按值查找和按位查找 ✅

//按位查找（静态分配的动态分配的都一样）
ElemType GetElem(SqList L,int i)
{
	return L.data[i-1];
}
 
//在顺序表L中查找第一个元素值等于e的元素，并返回其位置。
int LocateElem(SqList L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)
		{
			return i+1;//数组下标加一等于位序。
		}	
	}
	return 0;//退出循环，说明查找失败。	
}
 
//结构体的比较
/*
C语言里是不可以用 == 来比较两个结构体的，
需要依次对比各个分量来判断两个结构体是否相等。
假设有结构体a和b,有成员变量num和people
*/
 
if (a.num == b.num && a.people == b.people)
{
	printf("相等");
}
else
{
	printf("不相等");
}

单链表

定义结点及各名词的解释

typedef struct LNode
 //定义单链表结点类型，结构体名为LNode
{
    ElemType data;        //数据域，ElemType是element type（“元素的类型”）的意思
    struct LNode *next;   //指针域  
}LNode，*LinkList; 
 
/**
 *   LNode，*LinkList;两个都是是struct LNode的别名 
 *   展开即：
 *      typedef struct LNode LNode;
 *      typedef struct LNode* LinkList;
 *      *Linklist是当前这个结点的地址，这个结点里存储数据data和下一个结点的地址
 *       linklist：线性表
 * LNode：逻辑结点，结点的意思
 * 为什么要用两个别名呢？因为LNode * 强调连接关系，LinkList是头结点的意思，LinkList强调整个链表，通常用头指针代表整个链表。
使用LNode时，必须用 LNode *X,使用LinkList时必须用 LinkList X;
 * *next指向该结点下一个结点的地址 
 */

因为数据结构讨论的是抽象的数据结构和算法，大多数不针对某一类型进行讨论。一种结构中元素的类型不一定是整型、字符型、浮点型或者用户自定义类型，为了不重复说明，使用过程中用“elemtype”代表所有可能的数据类型，简单明了的概括了整体。在算法中，除特别说明外，规定ElemType的默认是int型。

增加一个新结点：

注意别忘了头文件。

这是一个模板，申请新结点都这样做：

struct  LNode *p = (struct LNode *) malloc (sizeof (struct LNode));
//在内存中申请一个结点所需的空间，并用指针P指向这个结点

【重要】

1、如果是涉及某一结点，就用 LNode * 函数名（LinkList L，…），如果是在整个链表上进行的操作，那么就是LinkList 函数名（LinkList L,…),例如：插入、查找值等都是LNode *函数名；头插法、尾插法建立单链表是LinkList 函数名()。

2、在涉及头部、尾部操作的时候，要注意一点：看看是否需要将插入的结点s p=s,L=s，什么的。

3、每次在对第i个进行操作时，要注意i是否合法，先判断合法性，再进行操作。

初始化单链表

//初始化一个空的单链表（不带头结点）
bool InitList(LinkList *L)
{
    L = NULL;//空表，暂时还没有任何结点，这里L是链表名
    return true;
}
//初始化一个单链表（带头结点）
bool InitList1(LinkList *L)
{
    L = (LNode *) malloc (sizeof(LNode));//分配一个头结点，这里L是头结点。
    if (L == NULL)
    {
        //内存不足，分配失败，这里用的是==，其余地方用=
       return false;
    }
    L -> next = NULL; //头结点之后暂时还没有结点
    return true;
}

头插法建立单链表

该方法从一个空表开始，生成新的结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点以后。

需要注意的是：

1、函数类型是LinkList。

2、每次新增加结点都需要动态申请一下结点。

3、一开始输入x的值是为插入找一个结束点，并不是真的值，后面建立好s结点【以后会再次输入x的值，覆盖掉。

4、注意L是一直指向头结点的，代表整个链表。

LinkList List_HeadInsert(LinkList L)
{
    int x;
    LNode *s;
    L= (LinkList) malloc(sizeof(LNode));
    L -> next = NULL;
    scanf("%d",&x);
 
    while (x <!= 999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;   
}

尾插法建立单链表

优点是结点插入的顺序和链表的顺序一致。该方法是将新结点插入到当前链表的表尾，因此必须有一个尾指针r。

需要注意的是

1、因为是尾插法，所以需要另外设置一个尾指针r来指向尾部。所以有三个指针，一个头指针指向头部，表示整个链表。一个尾指针指示待插入的部分，一个待插入的结点指针s。

2、每次插入完成后，都需要令r=s。也就是让尾指针后移指向最后的结点。别忘了rear->next = NULL。

LinkList List_RearInsert(LinkList L)
{
    int x;
    LNode *s,*r=L;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while (x != 999)
    {
       s= (LinkList)malloc(sizeof(LNode));
       s->data = x;
       scanf("%d",&x);
       r->next = s;
       r=s;
    }
    r->next = NULL;
    return L;
}

按序号查找结点值

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

需要注意的是：

1、因为是涉及结点，所以函数类型是LNode,如果用LNode那么函数名前面要加*。

2、记住该代码块的步骤！！！其他的都很类似。

3、按值查找：略。

LNode *getElem(int i,LinkList L)
{
    int j = 1;
    LNode *p = L->next;
    if (i < 1)
    {
        return NULL;
    }
    if (i  == 0)
    {
        return L;
    }
    
   while (p && j<i)
   {
        p = p->next;
        j++;
   }
   return p;
}

插入结点（p从头开始遍历时）

不带头结点

//第i个位置插入元素e,将要插入的结点称为s
bool ListInsert(LinkList *L,int i,ElemType e)
{
    if (i < 1)
    {
        return false;
    }
    if (i == 1)
    {
        //由于不带头结点，所以不存在所谓的第0个结点，因此i=1时需要特殊处理
        LNode *s = (LNode *) malloc (sizeof (LNode));
        s->data = e;
        s->next = L;//也就是在第一个结点的前面插入一个结点
        L = s;//头指针指向新结点
        return true;
    }
    LNode *p;//指针p当前扫描到的结点
    int j = 1;//当前p指向的是第几个结点
    p = L;    // L指向头结点，头结点是第0个结点（存数据）
    while (p != NULL && j < i-1)
    {
        //循环找到第i-1个结点
        p=p->next;
        j ++;
    }
    if (p == NULL)
    {
        return false;
    }
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

插入结点（p指向中间某结点）略

删除结点

1、查找结点，调用前面的函数。

2、不要忘了free结点。

p = GetElem(L,i-1);
q=p->next;
p->next = q ->next;
free(q);

双链表 

和单链表的操作几乎一致。略。

定义：

typedef int ElemType;
//双链表定义
typedef struct DNode
{
   ElemType data;
   struct DNode *prior, *next; 
}DNode,*DLinkList;

删除和插入操作与单链表的不同。注意！！！（希望每次有要插入删除的时候，自己在纸上画一画）。

循环单、双链表

略

静态链表

#define MaxSize 50
 
typedef int ElemType;
typedef struct 
{
    ElemType data;
    int next;//不是指针类型，是下一个元素的数组下标。
}SLinkList[MaxSize];
 

结束标准：next =-1.