线性表的链式表示和实现
/* 栈和队列应该是线性表的一种特殊形式，一个先进后出，一个先进先出,所以线性表有所有可能的情况 */#include<stdio.h>#include<malloc.h>struct node {int data;struct node *next;};/*将头结点和尾节点定为全局变量，这样就不要在函数间传来传去,还有p指针是用来遍历链表的*/ struct node *head,*tail,*pt;//定义一个全局变量n可以记录链表的节数 int n=0;void creatNode();void insertNode1(int i,int dta);void insertNode2(int num);void delNode1(int i);void delNode2(int dta); int length();void outNode(int i,int &da);void print();int main() {int i, da;/*===================================*//*验证creatNode函数初始化1,3,5,7,9*/ printf("初始化5个链表\n");for(i=1; i<=5; i++) {creatNode();printf("输入data：");scanf("%d", &tail->data);}print();printf("\n\n");/*===================================*/ /*===================================*/printf("在三个元素前插入4\n");insertNode1(3, 4);print();printf("\n\n");/*===================================*//*===================================*/printf("按元素大小插入6\n");insertNode2(6);print(); printf("\n\n");/*===================================*//*===================================*/printf("删除第三个节点\n");delNode1(3);print(); printf("\n\n");/*===================================*//*===================================*/printf("删除数据为5的节点\n");delNode2(5);print(); printf("\n\n");/*===================================*/ /*===================================*/printf("求链表的长度\n");printf("链表的长度为：%d\n", length()); printf("\n\n");/*===================================*//*====================================*/printf("取得第3个节点的数据\n");outNode(3, da);printf("%d\n", da); printf("\n\n");/*====================================*/}///////////////////////////////////////////////////////////////////// /*创建和初始化(尾插法建立一个单链表)，初始化最好不要在函数内部进行，一般在调用它的函数里面（main），然后把参数传进来就行了*/ void creatNode() {/*可以理解为一个固定模式，new一个新节点好的习惯是 p0->next = NULL*/ struct node *p0; p0 = (struct node*)malloc(sizeof(struct node));p0->next = NULL;//判断是否new成功 if(p0 == NULL) {printf("ERROR!");return;}/*如果开始时空表 (head没有初始化，系统默认为0，也就是NULL)*/ if(head == NULL) {head = p0;tail = p0;n ++;}else {//链表不为空 tail->next = p0;tail = p0;n ++;}}///////////////////////////////////////////////////////////////////*线性表的插入应该分两种情况，一个是按序号来插入，一个是根据大小排列来插入*/ /*按序号来插入，i插入的序号，dta插入的数据，比如i为5的话，那5和后面的数据向后移一位，可以理解为放在原表中第i的数据的前面*/ /*节点序号我从1开始，而且保证链表中至少有一个节点*/ void insertNode1(int i,int dta) {int k=1;//将传入的数据放入一个节点内 struct node *pd, *da;da = (struct node*)malloc(sizeof(struct node));da->next = NULL;da->data = dta;if(k == i) {//此时k=i=1，只有一个节点 da->next = head; head = da;n += 1; } else {//不止一个节点 pt = head;while(k<i) {pd = pt;//pd记录所插入序号节点的上一个节点 pt = pt->next;k ++;}pd->next = da;da->next = pt;n += 1;}} /*按大小来插入,num是要插入的数据，和链表里的数据比较大小，判断插入的位置，这里认为链表里的节点是按数据大小从小到大排列的*//*举几个特殊的例子将这个程序穿一遍,1.如果链表中只有一个节点，那num可插在这个节点的前面或后面，插前面：num不可能大于pt->data，while不执行，跳到下面if语句满足条件，而此时head==pt；所以执行if里面的if语句，最后节点数n加1.插后面：num大于pt->data,但此时pt->next == NULL,所以while还是不执行，跳到下面if语句，if语句不满足条件，执行else语句，pt->next=da,注意我再new节点是已经将da->next执行NULL2.链表有很多节点，num插在节点中间的某一个位置while会执行，有两种情况会跳出第一种：pt->next不等于NULL，但num<=pt->data,此时执行if语句里面的else语句第二种：num还大于pt->data,但pt->next==NULL，跳出，执行下面的else语句*/ void insertNode2(int num) {struct node *pd, *da;da = (struct node*)malloc(sizeof(struct node));da->next = NULL;da->data = num;pt = head;if(head == NULL) {//如果为空表，则将head指向插入的节点 head = da;tail = da;}else {//非空表（至少有一个节点） while(num>pt->data && pt->next != NULL) {pd = pt; //记录前一个节点 pt = pt->next;}if(num <= pt->data) {if(head == pt) {head = da;da->next = pt;}else {pd->next = da;da->next = pt;}}else {pt->next = da;tail = da;}}n += 1;} ///////////////////////////////////////////////////////////////////*删除某一个节点，两种情况：按序号删除和按元素删除这两种情况和插入里面的两种情况有相似之处，所以这里不再多说,这里假定链表中至少有一个节点，且i存在*///按序号 void delNode1(int i) {int k=1;struct node *pd;pt = head;if(head == NULL) {printf("链表为空\n");return;} while(k<i) {pd = pt;pt = pt->next;k ++;}if(k == i) {if(i == 1) {head = pt->next;}else {if(pt->next == NULL) {//如果删除的是尾节点的话，要改变tail指针 pd->next = NULL;tail = pd;}else {pd->next = pt->next;}}n -= 1;}else {printf("元素数据不存在\n");}}//按元素数据void delNode2(int dta) {struct node *pd;if(head == NULL) {printf("链表为空\n");return;}pt = head; while(dta != pt->data && pt->next != NULL) {pd = pt; //记录前一个节点 pt = pt->next;}if(dta == pt->data) {if(head == pt) {head = pt->next;}else {pd->next = pt->next;}n -= 1;}else {printf("此数据不存在\n");}} ////////////////////////////////////////////////////////////////// //求链表的长度 int length() {int n = 1;if(head == NULL)return 0; pt = head;while(pt->next != NULL){n ++;pt = pt->next;}return n;}////////////////////////////////////////////////////////////////////////// /*取出第i个个元素这里保证链表中至少有一个节点其实这里完全没必要那么麻烦，可以直接return 数据；，但此处要练习传引用*/ void outNode(int i,int &da) {int k=1;pt = head;if(i == k) {//此处i==k和i==1是等价的 da = pt->data;}while(k<i) {pt = pt->next;k ++;}da = pt->data;}////////////////////////////////////////////////////////////////////////// //遍历输出，供调试 void print() {pt = head;while(1) {printf("%d ", pt->data);if(pt->next == NULL) break;pt = pt->next;}printf("\n");}