
今天开始学习链表的部分
链表(linked list)分为很多种。有单链表和多链表等。结点(Node)的组成:线性表中的数据元素及元素之间的逻辑关系可有结点来表示。结点由两部分组成:一部分是用来存储数据元素的值的数据域,另一部分是用来存储元素之间逻辑关系的指针域,指针域存放的是该结点的直接后继结点的地址。结点的结构如图所示:
定义:用链式存储结构表示的线性表称为链表,即用一组任意(可以连续也可以不连续)的存储单元来存放线性表的结点;把每个结点只有一个指针域的链表称为单链表。
开始结点、尾结点、头结点、和头指针:
在链表中存储第一个数据元素的结点称为开始结点;存储最后一个数据元素的结点称为尾结点。在开始结点之前附加一个结点称为头结点;指向链表中第一个结点的指针称为头指针。
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;
}
原文始发于微信公众号(代码墙):数据结构学习笔记(二)