c语言描述：数据结构【三.线性表】（链表的使用）

刺骨的言语ヽ痛彻心扉 2022-11-01 13:57 108阅读 0赞

### 笔记目录 ###

*  前言
 *  结构体使用
 *  创造链表
 *  遍历链表数据
 *  判断是否为空以及测量长度
 *  插入数据
 *  删除数据

# 前言 #

这些代码均为自己在郝斌老师教学的基础下自己的理解与补充，以及一些详细的解释

# 结构体使用 #

#include<stdio.h>
    #include<malloc.h>
    # include <stdlib.h>
    typedef struct Node
    { 
       int data;
       struct Node *pnext
    }node,*pnode;
    /*相当于将node等价于struct Node, pnode等价于struct Node*/

# 创造链表 #

pnode create(void)
    { 
        int len,i,val;//分别存放有效节点个数，临时存放用户输入节点的值
        pnode phead=(pnode)malloc(sizeof(node));//分配头结点（不存放数据的），初始化
        if (NULL == phead)
        { 
           printf("分配失败, 程序终止!\n");
           exit(-1);
        }
        pnode ptail=phead;//相当于尾指针永远指向最后一个
        ptail->pnext=NULL;//此时ptail等同于pnext，则等于phead的初始化
        printf("请输入您需要生成的链表节点的个数: len = ");
    	scanf("%d", &len);
        for(i=0;i<len;i++)
        { 
           printf("请输入第%d个节点的值：",i+1);//从一开始数
           scanf("%d",&val);
           pnode pNew =(pnode)malloc(sizeof(node));
           	if (NULL == pNew)
    		{ 
    			printf("分配失败, 程序终止!\n");
    			exit(-1);
    		}
            pNew->data = val;
    		ptail->pnext = pNew;//相当于phead的尾节点指向了刚刚创造的链表
    		pNew->pnext = NULL;//保证新节点指向空，方便后面函数判断后面是否还有链表
    		ptail = pNew; //保持尾指针指向最后一个链表
        }
      return phead;//返回该链表头节点地址
    }

# 遍历链表数据 #

void traverse(pnode phead)
    { 
       pnode p=phead->pnext;//用一个新的指针指向头节点的下一个链表，头节点并不存储数据
       while(NULL!=p)
       { 
           printf("%d",p->data);
           p=p->pnext;//使得指针指向下一个
       }
       return;//用来终止程序
    
    }

# 判断是否为空以及测量长度 #

empty(pnode pHead)
    { 
    	if (NULL == pHead->pnext)//利用指向是否NUll来判断
    		return 1;
    	else
    		return 0;
    }
    length(pnode phead)
    { 
    	pnode p = phead->pnext;用一个新的指针指向头节点的下一个链表，头节点并不存储数据
    	int len = 0;
    
    	while (NULL != p)//仍不是到NULL则还有链表
    	{ 
    		++len;//自加
    		p = p->pnext;//指向下一个
    
    	}
    
    	return len;
    }

# 插入数据 #

insert(pnode pHead, int pos, int val)
    { 
    	int i = 0;
    	pnode p = pHead;
    
    	while (NULL!=p && i<pos-1)
    	{ 
    		p = p->pnext;
    		++i;
    	}//使得p指向所要插入位置的前一个位置
    
    	if (i>pos-1 || NULL==p)
        { 
            printf("出现错误，请检查所要插入位置");
    		return 0;
        }
    	//如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
    	//分配新的结点
    	pnode pNew = (pnode)malloc(sizeof(pnode));
    	if (NULL == pNew)
    	{ 
    		printf("动态分配内存失败!\n");
    		exit(-1);
    	}
    	pNew->data = val;
    	
    	//将新的结点存入p节点的后面
    	pnode q = p->pnext;//q指针指向了p的下个链表，即pos-1下一个链表，即pos（所要插入的地方）
        p->pnext = pNew;//将新创建的链表挂再p的下一个，即覆盖了pos处的链表地址
    	pNew->pnext = q;//将新创建的链表指向q（要插入处的链表）
    
    	return 1 ;
    }

# 删除数据 #

delete(pnode pHead, int pos, int * pVal)
    { 
    	int i = 0;
    	pnode p = pHead;
    
    	while (NULL!=p->pnext && i<pos-1)
    	{ 
    		p = p->pnext;//指向下一个链表
    		++i;
    	}
    
    	if (i>pos-1 || NULL==p->pnext)
    		return 0;
    	
    	//如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    	pnode q = p->pnext;  //q指向待删除的结点
    	*pVal = q->data;  
    
    	//删除p节点后面的结点
    	p->pnext = p->pnext->pnext;//相当于
    	
    	//释放q所指向的节点所占的内存
    	free(q);
    	q = NULL;
    	
    	return 1;
    
    }