线性表总结

线性表：线性表是由n个数据特性相同的元素组成的有限序列。它是学习其他数据结构的基础。线性表在计算机中可以用顺序存储和链式存储两种存储结构来表示。其中，用顺序存储结构表示的是顺序表，用链式存储结构表示的是链表。（链表又有单链表，双向链表，循环链表之分）

一些前提知识：

1，因为以后可能会对代码进行改变，所以可以提前定义好一些后期可能会变的量。

比如：数组的大小，arr[100]。那么可以在开头#define N 100.

比如：数组的数据类型，int arr[10]。那么可以在开头typedef int SQDataType

这样以后要改的话，就直接在宏定义上进行修改就可以了。

（类型的定义就用typedef，变量的定义就用define）

2，对线性表进行增删改查的时候用的都是接口函数。

3，结构体的定义：

//关于结构体的定义，假设原先结构体的名字是seq，你想改成S结构体的定义：Struct seq{};还有简便的是：Typedef struct seq{}S;Typedef struct seq S{};这样都把原来的名字改成了自己想用的名字。

一，顺序表

顺序存储结构，是指用一段地址连续的存储单元依次存储线性表的数据元素。实际上我们是用数组来实现这种结构的。顺序表又分为静态顺序表和动态顺序表。静态顺序表的容量大小在开始时就是已经定义好了的。而动态顺序表的容量大小则是可以改变的。（本文中代码实现的是动态顺序表）

静态顺序表的缺点：容量必须在一开始定义好，如果定义少了不够用，如果定义多了用不完浪费，不能灵活控制。

1，头文件

可以先将头文件写好，这个头文件也就是起一个将条件准备完整的作用，

定义好简便的，可以及时修改的符号变量，（常变量是用const来修饰的）

定义好顺序表的结构体（类型名，数组的类型，大小）

定义好要等会要用的接口。然后在C文件中进行解释说明就行了。

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1#pragma once//为了避免同一个头文件被包含（include）多次.#include//因为C文件代码定义中使用了assert断言，引一下。//常见的提前定义//#define MAX_SIZE 10   如果是用静态数组实现的顺序表就可以用这个宏的定义，动态数组实现的顺序表就不需要定义最大值了。#include#include#include#includetypedef int SQDataType;//定义线性表typedef struct SeqList{	SQDataType* a;//数组	int size;      //有效数据的个数	int capacity; //容量}SL;//增删改查等接口函数void SeqListInit(SL* ps);//初始化void SeqListPrint(SL* ps);//打印void SeqListDestroy(SL* ps);//销毁空间void SeqListPushFront(SL* ps, SQDataType x);//头插void SeqListPushBack(SL* ps, SQDataType x);//尾插void SeqListPopFront(SL* ps);//头删void SeqListPopBack(SL* ps);//尾删void SeqLisInsert(SL* ps, int pos, SQDataType x);//任意pos前插入数据void SeqListErase(SL* ps, int pos);//删除pos位置数据int  SeqListFind(SL* ps,SQDataType x);//查找x数据void SeqListModify(SL* ps, int pos, SQDataType x);//修改数据void SeqListCheckCapacity(SL* ps);//检查储存空间并扩充储存空间

2，C文件

c文件中主要是h中的接口的定义。

代码实现：

#include "SeqList.h"//引一下刚才定义好的头文件void SeqListInit(SL* ps)//初始化{	ps->a = NULL;	ps->size = 0;	ps->capacity = 0;		//刚开始可以不给空间，也可以给一点点空间，这里选择不给空间了。}void SeqListCheckCapacity(SL* ps)//检查储存空间并扩充储存空间{	if (ps->size >= ps->capacity)//如果存的数据大于等于数组的容量，这个时候有两种情况，一种就是原先的capacity就是空，那么无论存不存数据都会使这个条件成立。还有一种情况就是存储的数据真的超过了容量。这两种情况都需要扩容。	{		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//新建一个容量的数据，判断如果原先的数据是空，那么就直接分配4个数据，如果不是空，那么就把原来的数据变成扩两倍。		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));//使用realloc函数新建一个指定容量大小的空间。		if (tmp == NULL)		{			printf("realloc fail/n");			exit(-1);		}		else		{			ps->a = tmp;//将建好的空间赋给数组。			ps->capacity = newcapacity;//将新容量赋给旧r		}	}}void SeqListPushBack(SL* ps, SQDataType x)//尾插{    SeqListCheckCapacity(ps);	ps->a[ps->size] = x;	ps->size++;	//SeqListInsert(ps, ps->size, x);}void SeqListPrint(SL* ps)//打印{	for (int i = 0; i < ps->size; i++)	{		printf("%d ", ps->a[i]);		//数组是这个结构体的，这个数组不是多带带的个体，必须配合着ps结构体指针使用。	}	printf("/n");}void SeqListPushFront(SL* ps, SQDataType x)//头插{	SeqListCheckCapacity(ps);	int end = ps->size - 1;	//循环三要素：	//1，初始条件，2，结束条件，3，迭代过程。		while (end >= 0)	{		ps->a[end + 1] = ps->a[end];		end--;	} 	ps->a[0] = x;	ps->size++;    //用for也可以来实现：    /*	SeqListCheckCapacity(ps);		for (int i = ps->size-1; i >= 0; i--)		{			ps->a[i+1] = ps->a[i];		}	ps->a[0] = x;	ps->size++;*/	//前面的可以都不用，直接	//SeqListInsert(ps,0,x);}void SeqListPopBack(SL* ps)//尾删{	assert(ps->size > 0);    //这个断点的应用可以帮助找到在那一行出现的问题。	ps->size--;	//前面的可以都不用	//SeqListErase(ps,ps->size-1);	}void SeqListPopFront(SL* ps)//头删{	assert(ps->size > 0);	int start = 1;	while (start < ps->size)	{		ps->a[start - 1] = ps->a[start];		start++;	}	ps->size--;    /*这里也可以用for来实现	assert(ps->size > 0);	int i = 0;	for (i = 1; i <=ps->size; i++)	{		ps->a[i-1] = ps->a[i];	}	ps->size--;*/	//SeqListErase(ps,0);}void SeqListInsert(SL* ps, int pos, SQDataType x)//从中间插入{	assert(pos<ps->size);	SeqListCheckCapacity(ps);	int end = ps->size - 1;	while (pos <= end)	{		ps->a[end +1] = ps->a[end];		end--;	}	ps->a[pos] = x;	ps->size++;}void SeqListErase(SL* ps,int pos)//任意位置删除{    assert(pos < ps->size);	int start = pos + 1;	while (start < ps->size)	{		ps->a[start - 1] = ps->a[start];		start++;	}	ps->size--;}void SeqListDestroy(SL* ps)//空间的销毁{	free(ps->a);	ps->a = NULL;	ps->capacity = ps->size = 0;}int SeqListFind(SL* ps, SQDataType x)//查找{	for (int i= 0; i < ps->size; i++)	{		if (ps->a[i] == x)		{			return i;		}		}	return -1;}void SeqListModify(SL* ps, int pos, SQDataType x)//修改{	assert(pos < ps->size);	ps->a[pos] = x;}

3，测试菜单文件（menu）

写了个相关的小菜单，实现了一点人机交互。

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h";void menu(){	printf("************************************/n");	printf("1,尾插数据，        2，头插数据/n");	printf("3,尾删数据，        4，头删数据/n");	printf("5,在指定位置删数据， 6，在指定位置删除数据/n");	printf("7,查找数据，        8，打印数据/n");	printf("9,销毁表格，        0,修改表格/n");	printf(" -1，退出/n");	printf("请输入你的操作:/n");	printf("************************************/n");}int main(){ 	SL sl;	SeqListInit(&sl);	int option = 0;	int x = 0;	while (option != -1)	{		menu();		scanf("%d", &option);		switch (option)		{		case 1:			printf("请输入你要在表头插入的数据，以-1结束/n");			do			{				scanf("%d", &x);				if (x != -1)					SeqListPushBack(&sl, x);			} while (x != -1);			printf("已插入******/n");			break;		case 2:			printf("请输入你要在表头插入的数据，以-1结束/n");			do			{				scanf("%d", &x);				if (x != -1)				{					SeqListPushFront(&sl, x);				}			} while (x != -1);			printf("已插入******/n");			break;		case 3:			printf("您确定要删除表尾的数据吗？1：确定||2：否定/n");			int num1 = 0;			scanf("%d", &num1);			if (num1 == 1)			{				SeqListPopBack(&sl);				printf("已经删除******/n");				break;			}			else			break;		case 4:			printf("您确定要删除表头的数据吗？1：确定||2：否定/n");			int num2 = 0;			scanf("%d", &num2);			if (num2 == 1)			{				SeqListPopFront(&sl);				printf("已经删除******/n");				break;			}			else				break;			break;		case 5:			printf("请输入您要插入元素的位置/n");			int num5 = 0;			scanf("%d", &num5);			printf("您要插入的数据是：/n");			SQDataType x;			scanf("%d", &x);			SeqListInsert(&sl, num5,x);			printf("已插入******/n");			break;		case 6:			printf("请输入您要删除元素的位置/n");			int num6 = 0;			scanf("%d", &num6);			SeqListErase(&sl, num6);			printf("已删除******/n");			break;		case 7:			printf("请输入你要查找的数据：/n");			int num3 = 0;			scanf("%d", &num3);			int num4 = SeqListFind(&sl, num3);			if (num4 != -1)			{				printf("表中确实存在该数据,它的下标是：%d/n", num4);				break;			}			else				printf("抱歉，表中不存在该数据/n");			break;		case 8:			SeqListPrint(&sl);			break;		case 9:			printf("您确定要销毁表格吗？1：确定||2:否定/n");			int num9 = 0;			scanf("%d", &num9);			if (num9 == 1)			{				SeqListDestroy(&sl);				printf("已销毁******");				break;			}			else				break;		case 0:			printf("请输入您要修改的数据的位置：/n");			int num0 = 0;			scanf("%d", &num0);			printf("您要修改为的数据是：");			SQDataType x1;			scanf("%d", &x1);			SeqListModify(&sl, num0, x1);			printf("修改完毕******");			break;		case -1:			break;			default:			break;		}	}	SeqListDestroy(&sl);	return 0;}

4，顺序表的优缺点

优点：

1，无须为表示表中元素逻辑关系而增加额外的储存空间。

2，随机存取元素时可以达到O（1），效率高。

缺点：

1，插入和删除数据的时候需要移动大量的元素。

2，必须一开始就确定存储空间的容量。

3，如果空间不够了，增容。增容会付出一定性能的消耗，其次可能存在一定的空间浪费。（动态顺序表）

二，单链表

具体操作有：打印，尾插，头插，尾删，头删，在任意结点之前插入，删除任意结点，malloc一个新结点，在所给链表中查找数据x，并返回它的结点等。

标注的比较详细，可以借助注释食用哦。

分为三个项:（头文件，C文件，测试文件）

SList.h:包的引用和函数的声明

SList.c:各个操作的实现

Test.c:各个操作的实现

1，头文件

代码实现：

#pragma once//防止被重复包含#include#includetypedef int SLTDataType;struct SListNode{	SLTDataType data;             //链表的数据	struct SListNode* next;       //链表的指针};typedef struct SListNode  SLTNode;//改个名字//实现一些接口void SListPrint(SLTNode* phead);//打印void SListPushBack(SLTNode** pphead,SLTDataType);//尾插void SListPushFront(SLTNode** pphead, SLTDataType x);//头插void SListPopBack(SLTNode** pphead);//尾删void SListPopFront(SLTNode** pphead);//头删void SListInsert(SLTNode** pphead, int pos, SLTDataType x);//在任意位置插入void SListErase(SLTNode** pphead, int pos);//在任意位置删除SLTNode* BuySListNode(SLTDataType x);//malloc一个结点SLTNode* SListFind(SLTNode*phead, SLTDataType x);//在所给链表中查找数据x，并返回它的结点

2，C文件

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"//引一下头文件void SListPrint(SLTNode* phead)//打印，这个就是边遍历边打印{		SLTNode* cur = phead;//因为要通过指针遍历，所以就创建一个可移动的指针出来。	while (cur != NULL)	{		printf("%d->", cur->data)
            
                     

                 

                                                                                                                    
                         私有云
                                             
                         超融合服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               线性表顺序实现c语言
                                                                                                           c语言线性表删除数据
                                                                                                           线性表插入c语言
                                                                                                           线性表的顺序表c语言
                                                         
                 
               
              
             
               

                   
 文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
                 
                   
转载请注明本文地址：https://www.ucloud.cn/yun/121637.html
               
                      
               

                 
                                  
上一篇：C语言文件操作
  
                                                
                                       
下一篇：Linux——最全面试题整理（仅此一篇）