数据结构学习笔记(二)


今天开始学习链表的部分


链表的概念

链表(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("链表的长度为%dn", len);

 if(delete_list(pHead,2,&deleted_val)) {
   printf("删除成功,您删除的是%dn",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;
}





END


原文始发于微信公众号(代码墙):数据结构学习笔记(二)