便宜做网站8818,找马云做网站,免费好用的云电脑,网站附件下载表格怎么做顺序表和链表 1.线性表1.1顺序表1.1.1静态顺序表#xff08;不去实现#xff09;1.1.2动态顺序表1.1.2.1 定义程序目标1.1.2.2 设计程序1.1.2.3编写代码1.1.2.3测试和调试代码 1.1.2 顺序表的问题与思考 1.2链表1.2.1链表的概念及结构1.2.1.1 定义程序目标1.2.1.2 设计程序1.… 顺序表和链表 1.线性表1.1顺序表1.1.1静态顺序表不去实现1.1.2动态顺序表1.1.2.1 定义程序目标1.1.2.2 设计程序1.1.2.3编写代码1.1.2.3测试和调试代码 1.1.2 顺序表的问题与思考 1.2链表1.2.1链表的概念及结构1.2.1.1 定义程序目标1.2.1.2 设计程序1.2.1.3编写代码1.1.2.3测试和调试代码 1.线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 相同特性 逻辑结构人为想象出来的数据的组织形式 物理结构数据在想象出来的数据的组织形式。 1.1顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
1.1.1静态顺序表不去实现
#define N 5
typedef int SLdatatype;
typedef struct SeqList {SLdatatype array [N];int size;
};1.1.2动态顺序表
typedef int SLdatatype;
typedef struct SeqList {SLdatatype *arr;int capacity;//容量int size;//有效数据个数
}SL1.1.2.1 定义程序目标
#includestdio.h
#includestdlib.h
#includeassert.htypedef struct SeqList {SLDatatype *arr;int capacity;//容量int size;//有效数据个数
}SL;//初始化
void SLInitialize(SL*s);//销毁
void SLDestroy(SL*s );//打印顺序表
void SLPrint(SL* ps);//插入数据
//尾插
void SLPushBack(SL*s, SLDatatype x);//头插
void SLPushFront(SL*s, SLDatatype x);//尾删
void SLPopBack(SL* s);//头删
void SLPopFront(SL* s);//在指定位置插入数据
void SLInsert(SL* s, SLDatatype x, int pos);//在指定位置删除数据
void SLErase(SL* s,int pos);//查找数据
int SLFind(SL* s, SLDatatype x);1.1.2.2 设计程序
面向程序员自身的能实现包括顺序表的结构定义、初始化、插入、删除、查找、遍历、排序等操作
1.1.2.3编写代码
void SLInitialize(SL* ps)
{ps-arr NULL;ps-capacity ps-size 0;
}void SLDestroy(SL* ps)
{if (ps-arr){free(ps-arr);}ps-arr NULL;ps-capacity ps-size 0;
}void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps-size ps-capacity){//增容//若capacity为0给个默认值否则×2倍int NewCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;SLDatatype* tmp (SLDatatype*)realloc(ps-arr, NewCapacity * sizeof(SLDatatype));if (tmp NULL){perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity NewCapacity;}
}void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}void SLPushBack(SL*ps, SLDatatype x)
{assert(ps);SLCheckCapacity(ps);ps-arr[ps-size] x;
}void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);SLCheckCapacity(ps);//数据整体后移for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i-1];}ps-arr[0] x;ps-size;
}void SLPopBack(SL* ps)
{assert(ps ps-size);ps-size--;
}
void SLPopFront(SL* ps)
{assert(ps ps-size);for (int i 0; i ps-size-1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(pos 0 pos ps-size);SLCheckCapacity(ps);for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[ps-size] x;ps-size;}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size ps-size);for (int ipos; i ps-size-1; i){ps-arr[i] ps-arr[i1];}ps-size--;
}int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x)return i;}return -1;
}1.1.2.3测试和调试代码
#includeSeqlist.h
void SLtest01()
{SL s;SLInitialize(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushBack(s, 3);SLPushBack(s, 4);SLPushBack(s, 5);SLPushBack(s, 6);/*SLPushBack(NULL , 6);*/SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPushFront(s, 4);SLPrint(s); //4 3 2 1SLPopBack(s);SLPrint(s);SLPopBack(s);SLPrint(s);SLPopBack(s);SLPrint(s);SLPopBack(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLPopFront(s);SLPrint(s);SLInsert(s, 11, 0);SLPrint(s);SLInsert(s, 22, s.size);SLPrint(s);SLInsert(s, 33, 1);SLPrint(s);SLDestroy(s);
}int main()
{SLtest01();return 0;
}1.1.2 顺序表的问题与思考 中间/头部的插入删除时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们 再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。 1.2链表
1.2.1链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。
1.2.1.1 定义程序目标
实现
define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;//定义结点结构;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//链表的打印
void SLTPrint(SLTNode*);
//申请新结点
SLTNode* SLTBuyNode(SLTDataType);
//尾插
void SLTPushBack(SLTNode**, SLTDataType);
//头插
void SLTPushFront(SLTNode** , SLTDataType );//删除//尾删
void SLTPopBack(SLTNode**);
//头删
void SLTPopFront(SLTNode**);//查找
SLTNode* SLTFind(SLTNode*, SLTDataType);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);1.2.1.2 设计程序
面向程序员自身的能实现包括链表的结构定义、初始化、插入、删除、查找、遍历、排序等操作
1.2.1.3编写代码
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail);exit(1);}node-data x;node-next NULL;return node;
}void SLTPushBack(SLTNode**pphead, SLTDataType x)
{//申请新结点SLTNode*NewNode SLTBuyNode(x);if (*pphead NULL){*pphead NewNode;}//尾结点-新结点//找尾结点else{SLTNode* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next NewNode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请新结点SLTNode* NewNode SLTBuyNode(x);//进行头插NewNode-next *pphead;*pphead NewNode;
}void SLTPopBack(SLTNode** pphead)
{//链表为空不可以删除assert(pphead *pphead);//处理链表只有一个结点的情况if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//找prev和ptailSLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
}void SLTPopFront(SLTNode** pphead)
{//链表为空不可以删除assert(pphead *pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead NULL;*pphead next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;while (pcur){if (pcur-data x){return pcur;}else{pcur pcur-next;}}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead pos)SLTPushBack(pphead, x);else{SLTNode* prev *pphead;SLTNode* NewNode SLTBuyNode(x);while (prev-next ! pos){prev prev-next;}prev-next NewNode;NewNode-next pos;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* NewNode SLTBuyNode(x);NewNode-next pos-next;pos-next NewNode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead*pphead);assert(pos);if (*pphead pos)SLTPopBack(pphead);else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}void SListDestroy(SLTNode** pphead)
{SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}1.1.2.3测试和调试代码
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid SListTest01()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);//1-2-3-4-NULLSLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULLSLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTNode* find SLTFind(plist, 4);if (find NULL){printf(未找到\n);}else{printf(找到了\n);}SLTInsert(plist, plist, 11);//4-3-2-11-1-NULLSLTInsertAfter(plist, 11);SLTPrint(plist);1-11-2-3-4-NULLSLTErase(plist, plist);// 1-2-3-NULLSLTEraseAfter(plist);SLTPrint(plist);SListDestroy(plist);SLTPrint(plist);
}
int main()
{SListTest01();return 0;
}
