数据结构导论-2.2 线性表的链式储存之单链表

小鱼儿 2022-05-08 13:52 190阅读 0赞

**线性表的链式储存之单链表**

**单链表的类型定义：**

> typedef struct node
> 
> \{   DataType data; //数据域
> 
>     struct node \*next; //指针域
> 
> \}Node, \*LinkList;

**单链表举例**

学生档案信息表的链接存储实现

学生档案信息链表的类型完整描述如下：

> typedef struct
> 
> \{   int num; //学号
> 
>     char name\[8\]; //姓名
> 
>     int age; //年龄
> 
> \}DataType; //定义结点类型
> 
>  
> 
> typedef struct node
> 
> \{  datatype data ; //数据域
> 
>    struct node \*next;; //性表的实际长度
> 
> \}Node, \*LinkList; //Node是链表结点的类型
> 
> LinkList head;

**单链表的初始化:**

> LinkList InitiateLinkList ( ) //建立一个空的单链表
> 
> \{
> 
>     LinkList head; //头指针
> 
>     head= malloc(sizeof(Node)); //动态构建一结点，它是头结点;
> 
>     head->next=NULL;
> 
>     return head；
> 
> \}

**单链表的求表长:**

> int LengthLinkList1 (LinkList head)
> 
> \{     Node \*p=head; //p指向头结点
> 
>       int cnt=0; //计数器设初值
> 
>       while (p->next ! =NULL) //判断是否为尾结点
> 
>      \{    p=p->next; //指针移到下一个结点
> 
>           cnt++;
> 
>       \}
> 
>      return cnt; //返回表长
> 
> \}

**单链表的读表元素:**

> Node \*GetLinkList(LinkList head, int i)
> 
> //在单链表L中查找第i个元素结点，找到返回其指针，否则返回空
> 
> \{    Node \*p; //p是工作指针
> 
>      p=head->next; //初始时，p指向首结点
> 
>      int c=1;
> 
>      while (( c<i ) && (p!=NULL))
> 
>        \{p=p->next; c++; \}
> 
>      if (c==i) return p; //找到
> 
>      else return NULL; //查找失败
> 
> \}

**单链表的定位:**

> Int LocateLinkList( LinkList head, DataType x)
> 
> //在单链表head中查找第一个值为x的结点，找到后返回其序号，否则返回0
> 
> \{      Node \*p=head;
> 
>        p=p->next;
> 
>        int i=0;
> 
>        while (p!=NULL && p->data!= x)
> 
>         \{i++;
> 
>         p=p->next; \}
> 
>        if (p!=NULL) return i+1;
> 
>        else return 0;
> 
> \}

**单链表的插入:**

> void InsertLinkList( LinkList head, DataType x, int i)
> 
> //在单链表head的第i个位置上插入值为x的元素
> 
> \{ Node \*p,\*q;
> 
> if (i==1) q=head;
> 
> else q=GetLinkList(head, i-1); //查找第i-1个结点
> 
> if (q==NULL)
> 
> exit("找不到插入位置"); //第i-1个不存在不能插入
> 
> else
> 
> \{p=malloc(sizeof(Node)); //申请、填装结点
> 
> p->data=x;
> 
> p->next=q->next; //新结点插入在第i-1个结点的后面
> 
> q->next=p;
> 
> \}
> 
> \}

**单链表的删除:**

> void DeleteLinkList(LinkList head，int i)
> 
> //删除单链表head上的第i个数据结点
> 
> \{ Node \*q,\*p
> 
> if (i==1) q=head;
> 
> else q=GetLinkList(head, i-1); //查找第i-1个结点
> 
> if (q != NULL&& q->next !=NULL)
> 
>   \{ p=q->next; //p指向第i个结点
> 
>     q->next=p->next; //从链表中删除p
> 
>     free(p); //释放\*p
> 
>   \}
> 
> else exit("第i个结点不存在");
> 
> \}