C语言实现数据结构的链表

川长思鸟来 2022-09-18 07:57 179阅读 0赞

链表是用一组任意的存储单元来存放线性表的结点.

为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址信息,这个信息称为指针或链

下面是C语言实现链表的数据结构及基本的算法。

\# include <stdio.h>  
\# include <stdlib.h>  
typedef char DataType;   //定义节点数据域类型  
typedef struct node      //节点类型定义  
\{  
 DataType data;      //节点的数据域  
 struct node \*next;  //节点的指针域指向下一个节点  
\}ListNode;  
typedef ListNode \*LinkList;   
ListNode \*p;   //定义节点指针  
LinkList head; //定义链表头指针

/\*错误信息输出函数\*/  
void Error(char \*message)  
\{  
 fprintf(stderr,"Error:%s/n",message); //输出错误信息  
 exit(1);//终止程序，返回1给操作系统  
\}

/\*打印输出链表\*/  
void printList(LinkList head)  
\{  
 ListNode \*p; //节点  
 int i=0;  
 if(head!=NULL)  
 \{  
  p=head;  
  while(p->next!=NULL)  
  \{  
   p=p->next;  
   printf("node\[%d\]=%c/n",i,p->data);  
   i++;  
  \}  
    
 \}  
\}

/\*创建链表\*/  
LinkList CreateList()  
\{  
 char ch;  
 LinkList head=(LinkList)malloc(sizeof(ListNode));//生成头节点  
 ListNode \*s,\*r;  
 r=head;  
 head->data='\*';  
 while((ch=getchar())!='/n')  
 \{  
  s=(LinkList)malloc(sizeof(ListNode));  
  s->data=ch;  
  r->next=s;  
  r=s;  
 \}  
 r->next=NULL;  
 return head;  
\}

/\*取得第i个结点\*/  
ListNode \* getNode(LinkList head,int i)  
\{  
 int j=0;  
 ListNode \*p;  
 p=head;  
 while(p->next!=NULL)  
 \{  
  p=p->next;  
  j++;  
  if(j==i)  
  \{  
   return p;  
  \}  
 \}  
 return NULL;  
\}

/\*根据结点值域找到结点\*/  
ListNode \* getNodeByKey(LinkList head,DataType key)  
\{  
 int j=0;  
 ListNode \*p;  
 char nodeData;  
 p=head;  
 while(p->next!=NULL)  
 \{  
  p=p->next;  
  nodeData=p->data;  
  if(key==nodeData)  
  \{  
   return p;  
  \}  
 \}  
 return NULL;  
\}  
/\*插入结点\*/  
void insertList(LinkList head,DataType x,int i)  
\{  
 ListNode \*p,\*s;  
 p=getNode(head,i-1);  
 if(p==NULL)  
 \{  
  Error("position error");  
 \}  
 s=(ListNode \*)malloc(sizeof(ListNode));  
 s->data=x;  
 s->next=p->next;  
 p->next=s;  
\}

/\*删除结点\*/  
void deleteList(LinkList head,int i)  
\{  
 ListNode \*p,\*r;  
 p=getNode(head,i-1);  
 if(p==NULL||p->next==NULL)  
 \{  
  Error("position error");  
 \}  
 r=p->next;  
 p->next=r->next;  
 free(r);  
\}

void main()  
\{  
 LinkList list;  
 ListNode \*node;  
 int getIndex=4;  
 list=CreateList(); //创建链表  
 printList(list);    
 node=getNode(list,getIndex);  //取得链表中索引为4的节点  
 printf("get node%d is%c/n",getIndex,node->data);  
 printf("insert X to node %d/n",3);  
 insertList(list,'X',3); //在索引为3的地方插入节点  
 printList(list);  
 printf("delete %d node/n",3);  
 deleteList(list,3);   //删除索引为3的节点  
 printList(list);  
\}