一 顺序表的定义和实现1.顺序表的定义顺序表是线性表的一种存储结构其逻辑结构和物理结构都为线性采用连续的物理存储单元依次存放物理元素其底层结构是数组。2.顺序表的分类顺序表底层结构为数组数组是一段连续的地址空间我们在申请空间时可以直接申请一个数组也可以使用内存分配函数申请一块大小不确定的内存空间所以顺序表可以分为静态顺序表和动态顺序表。1静态顺序表structSeqList{intarr[100];intsize;};2动态顺序表structSeqList{SLDataType*arr;intsize;intcapacity;}SL;3.顺序表的功能对顺序表中的数据我们可以进行增删查改等操作对顺序表也可以进行初始化与销毁。顺序表的初始化与销毁//顺序表初始化与销毁voidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}voidSLDestory(SL*ps){if(ps-arr){free(ps-arr);}ps-arrNULL;ps-sizeps-capacity0;}2.顺序表的增删查改//顺序表的增容voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;SLDataType*tmp(SLDataType*)realloc(ps-arr,newCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}}//顺序表的头插尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps-arr[ps-size]x;ps-size;}voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;ps-size;}//顺序表的删除voidSLPopBack(SL*ps){assert(ps);assert(ps-size);ps-size--;}voidSLPopFront(SL*ps){assert(ps);assert(ps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}//在指定位置插入voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}//删除指定位置数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}//查找intSLFind(SL*ps,SLDataType x){assert(ps);for(inti0;ips-size;i){if(ps-arr[i]x){returni;}}return-1;}//顺序表的打印voidSLPrint(SL s){for(inti0;is.size;i){printf(%d ,s.arr[i]);}printf(\n);}二 顺序表的应用基于顺序表实现通讯录上边我们实现了顺序表的基本功能现在可以在顺序表的基础上增加一些功能实现一个简易的通讯录。定义Contact.h 实现通讯录联系人结构体定义声明通讯录的功能。#pragmaonce#defineNAME_MAX20#defineGENDER_MAX10#defineTEL_MAX20#defineADDR_MAX100//创建联系人结构体typedefstructpersonInfo{charname[NAME_MAX];chargender[GENDER_MAX];intage;chartel[TEL_MAX];charaddr[ADDR_MAX];}peoInfo;//给顺序表改个名字typedefstructSeqListContact;//通讯录的初始化与销毁voidContactInit(Contact*con);voidContactDestory(Contact*con);//联系人的增加voidContactAdd(Contact*con);//联系人的删除voidContactDel(Contact*con);//联系人的修改voidContactModify(Contact*con);//联系人的查找voidContactFind(Contact*con);//展示通讯录voidContactShow(Contact*con);添加Contact.c 实现通讯录各个功能。#includeContact.h#includeSeqList.h//通讯录的初始化与销毁voidContactInit(Contact*con){SLInit(con);}voidContactDestory(Contact*con){SLDestory(con);}//联系人的增加voidContactAdd(Contact*con){peoInfo info;printf(请输入要添加的联系人姓名\n);scanf(%s,info.name);printf(请输入要添加的联系人性别\n);scanf(%s,info.gender);printf(请输入要添加的联系人年龄\n);scanf(%d,info.age);printf(请输入要添加的联系人电话\n);scanf(%s,info.tel);printf(请输入要添加的联系人地址\n);scanf(%s,info.addr);SLPushBack(con,info);}//通过姓名查找intFindbyname(Contact*con,charname[]){for(inti0;icon-size;i){if(0strcmp(con-arr[i].name,name)){returni;}}return-1;}//联系人的删除voidContactDel(Contact*con){charname[NAME_MAX];printf(请输入你要删除的联系人姓名\n);scanf(%s,name);intfindFindbyname(con,name);if(find0){printf(要删除的联系人不存在\n);}else{SLErase(con,find);}}//联系人的修改voidContactModify(Contact*con){charname[NAME_MAX];printf(请输入你要修改的联系人姓名\n);scanf(%s,name);intfindFindbyname(con,name);if(find0){printf(要修改的联系人不存在\n);}else{printf(请输入新的联系人姓名\n);scanf(%s,con-arr[find].name);printf(请输入新的联系人性别\n);scanf(%s,con-arr[find].gender);printf(请输入新的联系人年龄\n);scanf(%d,con-arr[find].age);printf(请输入新的联系人电话\n);scanf(%s,con-arr[find].tel);printf(请输入新的联系人住址\n);scanf(%s,con-arr[find].addr);printf(修改成功\n);}}//联系人的查找voidContactFind(Contact*con){charname[NAME_MAX];printf(请输入你要查找的联系人姓名\n);scanf(%s,name);intfindFindbyname(con,name);if(find0){printf(要查找的联系人不存在\n);}else{printf(姓名 性别 年龄 电话 地址\n);printf(%s %s %d %s %s\n,con-arr[find].name,con-arr[find].gender,con-arr[find].age,con-arr[find].tel,con-arr[find].addr);}}//展示通讯录voidContactShow(Contact*con){printf(姓名 性别 年龄 电话 地址\n);for(inti0;icon-size;i){printf(%s %s %d %s %s\n,con-arr[i].name,con-arr[i].gender,con-arr[i].age,con-arr[i].tel,con-arr[i].addr);}}添加test.c 文件测试功能。#includeSeqList.hvoidmenu(){printf(***************通讯录****************\n);printf(*******1增加数据 2删除数据********\n);printf(*******3修改数据 4查找数据********\n);printf(*******5展示通讯录 0退出 ********\n);printf(*************************************\n);}intmain(){Contact con;ContactInit(con);intinput;do{menu();printf(请选择你的操作\n);scanf(%d,input);switch(input){case1:ContactAdd(con);break;case2:ContactDel(con);break;case3:ContactModify(con);break;case4:ContactFind(con);break;case5:ContactShow(con);break;default:break;}}while(input);ContactDestory(con);return0;}三 单链表定义1.单链表的定义单链表是线性表的一种链式存储结构其逻辑结构呈线性排列但物理存储上节点之间并非连续。单链表由多个节点串联而成每个节点包含数据域和指针域其中指针域存储着下一个节点的地址信息。如图所示2.单链表的实现我们需要定义单链表就要定义单链表里的节点节点分为数据域和指针域。//创建节点结构体typedefintSLTDataType;typedefstructSListNode{SLTDataType data;structSListNode*next;}SLTNode;3.单链表的功能单链表和顺序表一样可以对其中数据进行增删查改等操作。#includeSList.h//单链表的打印voidSLTPrint(SLTNode*phead){SLTNode*pucr;pucrphead;while(pucr){printf(%d-,pucr-data);pucrpucr-next;}printf(NULL\n);}//申请新节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}//单链表的头插尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x){//先申请一个新节点assert(pphead);SLTNode*newnodeSLTBuyNode(x);//空链表和非空链表两种情况if(*ppheadNULL){*ppheadnewnode;}else{SLTNode*ptail;ptail*pphead;while(ptail-next!NULL){ptailptail-next;}ptail-nextnewnode;}}voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;//先将新节点与原链表连接*ppheadnewnode;//再让头指针指向链表第一个节点newnode}//单链表的头删尾删voidSLTPopBack(SLTNode**pphead){assert(pphead*pphead);//若链表只有一个节点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{//先找到尾节点再将其释放SLTNode*ptail*pphead;SLTNode*prev*pphead;while(ptail-next!NULL){prevptail;ptailptail-next;}free(ptail);ptailNULL;prev-nextNULL;}}voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next;next(*pphead)-next;free(*pphead);*ppheadnext;}//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcurphead;while(pcur){if(pcur-datax){returnpcur;}pcurpcur-next;}returnNULL;}//链表在指定位置之前插入voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead*pphead);assert(pos);//在第一个节点之前插入if(pos*pphead){SLTPushFront(pphead,x);}else//在其他位置插入{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}SLTNode*newnodeSLTBuyNode(x);prev-nextnewnode;newnode-nextpos;}}//链表在指定位置之后插入voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnodeSLTBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}//删除pos位置的数据voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(pphead*pphead);assert(pos);if(*ppheadpos){SLTPopFront(pphead);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}prev-nextpos-next;free(pos);posNULL;}}//删除pos位置之后的数据voidSLTEraseAfter(SLTNode*pos){assert(pospos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}//销毁链表voidSlistDestory(SLTNode**pphead){assert(pphead*pphead);SLTNode*pcur*pphead;while(pcur){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}