数据结构学习(2)--链表

今天开始学习链表的部分

链表的概念

链表(linked list)分为很多种。有单链表和多链表等。结点(Node)的组成：线性表中的数据元素及元素之间的逻辑关系可用结点来表示。结点由两部分组成：一部分是用来存储数据元素的值的数据域，另一部分是用来存储元素之间逻辑关系的指针域，指针域存放的是该结点的直接后继结点的地址。结点的结构如图所示：

单链表(Single Linked List)

定义：用链式存储结构表示的线性表称为链表，即用一组任意(可以连续也可以不连续)的存储单元来存放线性表的结点；把每个结点只有一个指针域的链表称为单链表。

开始结点、尾结点、头结点、和头指针：
在链表中存储第一个数据元素的结点称为开始结点；存储最后一个数据元素的结点称为尾结点。在开始结点之前附加一个结点称为头结点；指向链表中第一个结点的指针称为头指针。

实战

typedef struct Node {
   int data;
   struct Node * pNext;
}NODE, * PNODE; //NODE等价于struct Node，PNODE等价于struct Node *

用结构体表示结点的指针域和数据域。通过typedef定义NODE和* PNODE。这里的NODE等价于struct Node，PNODE等价于struct Node *

PNODE createList() {
   int len;
   int i;
   int val;
   PNODE pHead = (PNODE)malloc(sizeof(NODE)); // 等价于 struct Node * pHead = (struct Node *) mallc(sizeof(struct Node));
   PNODE pTail = pHead; //等价于 struct Node * pTail = 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; // 尾指针指向新结点，这样就将每个结点连起来了
       pNew->pNext = NULL; 
       pTail = pNew; // 尾结点指向最后的有效结点
   }
   return pHead;
}

整个的创建链表的流程，如图所示

接下来，模仿创建链表的逻辑，模仿写出如下函数：

void traverseList(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE); //求链表长度
bool insert_list(PNODE,int,int); //链表，位置，值
bool delete_list(PNODE, int ,int *);
void sort_list(PNODE);

全部代码

#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 createList();
void traverseList(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE); //求链表长度
bool insert_list(PNODE,int,int); //链表，位置，值
bool delete_list(PNODE, int ,int *);
void sort_list(PNODE);


int main() {
 int deleted_val;
   PNODE pHead = NULL; //将头结点设为空 
   pHead = createList(); // 创建链表
   traverseList(pHead);
 int len = length_list(pHead);
 printf("链表的长度为%d\n", len);


 if(delete_list(pHead,2,&deleted_val)) {
   printf("删除成功，您删除的是%d\n",deleted_val);
 
 }else {
   printf("删除失败!\n");
 }
 traverseList(pHead);
 
 return 0;
}


// 创建链表
PNODE createList() {
   int len;
   int i;
   int val;
   PNODE pHead = (PNODE)malloc(sizeof(NODE)); // 等价于 struct Node * pHead = (struct Node *) mallc(sizeof(struct Node));
   PNODE pTail = pHead; //等价于 struct Node * pTail = 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; // 尾指针指向新结点，这样就将每个结点连起来了
   pNew->pNext = NULL; 
       pTail = pNew; // 尾结点指向最后的有效结点
   }
   return pHead;
}


// 遍历链表
void traverseList(PNODE pHead) {
   PNODE p = pHead->pNext;


   while(NULL != p) {
       printf("%d ",p->data);
       p = p->pNext;
   }
   printf("\n");


 return;
}


// 是否为空
bool is_empty(PNODE pHead) {
 if(NULL == pHead->pNext) {
   return true;
 }else {
   return false;
 }
}


// 返回链表长度
int length_list(PNODE pHead) {
 PNODE p = pHead->pNext;
 int len = 0;
 while(NULL != p) {
   ++len;
   p = p->pNext;
 }


 return len;
}


/*
 排序
*/
void sort_list(PNODE pHead) {
 
 int i,j,t;


 PNODE p,q;


 int len = length_list(pHead); 
 
 for(i = 0,p = pHead->pNext;i < len - 1; ++i,p = p->pNext) {
   for(j = i + 1,q = p->pNext; j < len; ++j,q = q->pNext) {
     if(p->data > q->data) {
       t = p->data;
       p->data = q->data;
       q->data = t;
     }
   }
 }
 return;
}


/**
 插入节点
*/
bool insert_list(PNODE pHead, int pos, int val) {
 
 int i = 0;
 PNODE p = pHead;
 
 while(NULL != p && i < pos -1) {
   p = p->pNext;
   ++i;
 }


 if(i > pos - 1 || NULL == p) {
   return false;
 }


 PNODE pNew = (PNODE)malloc(sizeof(NODE));


 if(NULL == pNew) {
   printf("动态内存分配失败!\n");
   exit(-1);
 }
 pNew->data = val;
 PNODE q = p->pNext;
 p->pNext = pNew;
 pNew->pNext = q;
}
bool delete_list(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) {
   return false;
 }
 
 PNODE q = p->pNext;
 *pVal = q->data;


 //删除p节点后面的节点
 p->pNext = p->pNext->pNext;
 free(q);
 q = NULL;


 return true;
}