顺序表和单链表的代码实现_业界新闻

发布时间:2024-07-29 20:58

阅读量:0

需要代码并且需要运行结果的可以进入链接自行领取。

顺序表：是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

链表：是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

1.SeqList.h

#pragma once  #include<stdio.h> #include<stdlib.h> #include<assert.h>  typedef int SLDataType; #define INIT_CAPACITY 4  typedef struct S { 	SLDataType* a; 	int sz; 	int capacity; }SL;  //顺序表的初始化 void SLInit(SL* pc);  //尾插 void SLPushBack(SL* pc,SLDataType x);  //尾删 //void SLPopback(SL* pc);  //扩容 void SLCheckCapacity(SL* pc);  //插入 void SLInsert(SL* pc,int pos,SLDataType x);  //查找 void SLFine(SL* pc, SLDataType x);  //删除 void SLErase(SL* pc, int pos);  //打印 void SLPrint(SL* pc);  //修改 void SLModify(SL* pc, int pos, SLDataType x);  //销毁 void SLDestroy(SL* pc);

2.Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1  #include"SeqList.h"   void SLCheckCapacity(SL* pc) { 	assert(pc);  	if (pc->sz == pc->capacity) 	{ 		SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2); 		if (tmp == NULL) 		{ 			perror("realloc"); 			return; 		} 		pc->a = tmp; 		pc->capacity *= 2; 	} }  void SLInit(SL* pc) { 	pc->a = (SLDataType*)malloc(sizeof(SLDataType*)*INIT_CAPACITY); 	if (pc->a == NULL) 	{ 		perror("malloc"); 		return; 	} 	pc->sz = 0; 	pc->capacity = INIT_CAPACITY; }  void SLPushBack(SL* pc,SLDataType x) { 	SLCheckCapacity(pc); 	pc->a[pc->sz] = x; 	pc->sz++; }   void SLPrint(SL* pc) { 	for (int i = 0; i < pc->sz; i++) 	{ 		printf("%d ", pc->a[i]); 	} 	printf("\n"); }  void SLDestroy(SL* pc) { 	assert(pc); 	free(pc->a); 	pc->a = NULL; 	pc->sz = pc->capacity = 0; }  void SLInsert(SL* pc,int pos, SLDataType x) { 	assert(pc); 	assert(pos >= 0 && pos <= pc->sz); 	//扩容 	SLCheckCapacity(pc);  	int end = pc->sz - 1; 	while (end >= pos) 	{ 		pc->a[end + 1] = pc->a[end]; 		end--; 	} 	pc->a[pos] = x; 	pc->sz++; }   void SLErase(SL* pc,int pos) { 	assert(pc); 	assert(pos >= 0 && pos < pc->sz); 	int begin = pos; 	while (begin < pc->sz - 1) 	{ 		pc->a[begin] = pc->a[begin + 1]; 		begin++; 	} 	pc->sz--; }  void SLFine(SL* pc, SLDataType x) { 	assert(pc);  	for (int i = 0; i < pc->sz; i++) 	{ 		if(pc->a[i] == x) 			return i; 	} 	return -1; }  void SLModify(SL* pc, int pos, SLDataType x) { 	assert(pc); 	assert(pos >= 0 && pos < pc->sz); 	pc->a[pos] = x; }

链表的实现

1.SList.h

#define _CRT_SECURE_NO_WARNINGS 1  #include <stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTistDataType;  typedef struct SListNode { 	SLTistDataType data; 	struct SListNode* next; }SLTNode;   //打印 void SLTPrint(SLTNode* phead);  //尾插 void SLTPushBack(SLTNode** pphead, SLTistDataType x);  //尾删 void SLTPopBack(SLTNode** pphead);  //头插 void SLTPushFront(SLTNode** pphead, SLTistDataType x);  //头删 void SLTPopFront(SLTNode** pphead);  //查找 SLTNode* SLTFind(SLTNode* phead, SLTistDataType x);  //在pos前插入 void SLTInsert(SLTNode** pphead, SLTNode *pos, SLTistDataType x);  //在pos处删除 void SLTErase(SLTNode** pphead, SLTNode* pos);

2.SList.c

#define _CRT_SECURE_NO_WARNINGS 1  #include"SList.h"  void SLTPrint(SLTNode* phead) { 	SLTNode* str = phead; 	while (str) 	{ 		printf("%d->", str->data); 		str = str->next; 	} 	printf("NULL\n"); }  SLTNode* NewSLTNode(SLTistDataType x) { 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); 	if (newnode == NULL) 	{ 		perror("malloc"); 		return NULL; 	} 	newnode->data = x; 	newnode->next = NULL; 	return newnode; }  void SLTPushBack(SLTNode** pphead, SLTistDataType x) { 	SLTNode* tail = *pphead; 	/*SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode)); 	if (newnode == NULL) 	{ 		perror("malloc"); 		return; 	}*/ 	SLTNode* newnode = NewSLTNode(x); 	if (*pphead == NULL) 	{ 		*pphead = newnode; 	} 	else 	{ 		while (tail->next != NULL) 		{ 			tail = tail->next; 		} 		tail->next = newnode; 	} 	/*newnode->data = x; 	newnode->next = NULL;*/ }   void SLTPopBack(SLTNode** pphead) { 	//断言 	assert(*pphead);  	if (*pphead == NULL) 	{ 		return; 	} 	if ((*pphead)->next = NULL) 	{ 		free(*pphead); 		*pphead = NULL; 		return; 	} 	else 	{ 		/*SLTNode* pre = *pphead; 		SLTNode* tail = *pphead; 		while (tail->next != NULL) 		{ 			pre = tail; 			tail = tail->next; 		} 		free(tail); 		tail = NULL; 		pre->next = NULL;*/ 		 		SLTNode* tail = *pphead; 		while (tail->next->next != NULL) 		{ 			tail = tail->next; 		} 		free(tail->next); 		tail->next = NULL; 	} }   void SLTPushFront(SLTNode** pphead, SLTistDataType x) { 	SLTNode* newnode = NewSLTNode(x); 	newnode->next = *pphead; 	*pphead = newnode; }  void SLTPopFront(SLTNode** pphead) { 	//暴力检查 	assert(*pphead);  	if (*pphead == NULL) 	{ 		return; 	}  	/*SLTNode* frist = *pphead; 	*pphead = frist->next; 	free(frist); 	frist = NULL;*/ 	SLTNode* frist = *pphead; 	*pphead = (*pphead)->next; 	free(frist); 	frist = NULL; }  SLTNode* SLTFind(SLTNode* phead, SLTistDataType x) { 	SLTNode* cur = phead; 	while (cur) 	{ 		if (cur->data == x) 		{ 			return cur; 		}  		cur = cur->next; 	}  	return NULL; }  void SLTInsert(SLTNode** pphead, SLTNode *pos, SLTistDataType x) { 	assert(pos); 	assert(pphead);  	if (pos == *pphead) 	{ 		SLTPushFront(pphead, x); 	} 	else 	{ 		// 找到pos的前一个位置 		SLTNode* prev = *pphead; 		while (prev->next != pos) 		{ 			prev = prev->next; 		}  		SLTNode* newnode = NewSLTNode(x); 		prev->next = newnode; 		newnode->next = pos; 	} }  void SLTErase(SLTNode** pphead, SLTNode* pos) { 	assert(pphead); 	assert(pos); 	assert(*pphead);  	if (pos = *pphead) 	{ 		SLTPopFront(pphead); 	}  	SLTNode* cur = *pphead; 	while (cur->next != pos) 	{ 		cur = cur->next; 	} 	cur->next = pos->next; 	free(pos); 	pos = NULL;  }