数据结构入门-离散存储(链表)
有什么问题可以在下面讨论，
一、预备知识：typedef
基本使用
#include
typedef int AAA; // 为int再重新取一个名字，AAA就等于int
typedef struct Student
{
int sid;
char name[100];
char sex;
}ST;
int main(void)
{
int i = 10; // 等价于 AAA = 10;
struct Student st; // 等价于 ST st;
struct Student * ps = &st; // 等价于 ST * ps = &st;
ST st2;
st2.sid = 10;
printf("%d \n", st2.sid);
return 0;
}
也可以这样使用，这样更加的方便
#include
typedef struct Student
{
int sid;
char name[100];
char sex;
}* PST; // PST等价于 typedef struct *
int main(void)
{
struct Student st;
PST ps = &st;
ps->sid = 99;
printf("%d\n", ps->sid);
return 0;
}
还可以把上面的两个结合起来
#include
typedef struct Student
{
int sid;
char name[100];
char sex;
}* PST , STU; // PST等价于 typedef struct * , STU代表了typedef struct
int main(void)
{
STU st; // 等价于struct Student st
PST ps = &st;
ps->sid = 99;
printf("%d\n", ps->sid);
return 0;
}
二、离散存储(链表)
定义：n个节点离散分配，彼此通过指针相连，每一个节点只有一个前驱节点和一个后续节点，首节点没有前驱节点，尾节点没有后续节点
专业术语：
首节点：第一个有效节点
尾节点：最后一个有效节点
头节点：首节点前面
头指针：指向头节点的指针变量
尾指针：指向尾节点的指针变量
注意：头节点的数据类型和首节点类型一样，头节点里面没有存放有效数据，没有实际含义，为了方便对链表的操作
如果通过希望一个函数来对链表进行处理，我们至少需要接收链表的那些参数
只需要一个参数：头指针
因为我们可以通过头指针推算出链表的其他所有参数
每一个链表节点的数据类型如何表示
#include
typedef struct Node
{
int data; // 数据域
struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点
}NODE , *PNODE;
// NODE 等价于struct Node
// PNODE 等价于struct Node *
int main(void)
{
return 0;
}
分类：
单链表
双链表：每一个节点有两个指针域
循环链表：能通任何一个节点找到其他所有的节点
非循环链表
算法：
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
算法
狭义的算法是与数据的存储方式密切相关
广义的算法与数据的存储方式无关
泛型
利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的
多敲代码，熟练的掌握，并进行改进
#include
#include
#include
typedef struct Node
{
int data;
struct Node * pNext;
}NODE , *PNODE; // NODE等价于struct Node ， PNODE等价于struct Node *
PNODE create_list(void);
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
bool insert_list(PNODE , int ,int); // 第二个是插入位置，第三个是插入的值
bool delete(PNODE , int, int*); // 第二个是删除的位置，第三个是所删除位置的值
void sort_list(PNODE pHead);
int main(void)
{
PNODE pHead = NULL; // 等价于struct Node * pHead = NULL;
pHead = create_list(); // 创建一个非循环单链表，并将该链表的头节点地址付给pHead
// if(is_empty(pHead))
// printf("链表为空\n");
// else
// printf("链表不为空\n");
// printf("链表的长度为%d\n", length_list(pHead) );
// sort_list(pHead);
insert_list(pHead , 4, 99);
int val;
if(delete(pHead, 1 , &val))
{
printf("删除成功，你删除的是%d\n", val);
}
else
{
printf("删除失败\n");
}
traverse_list(pHead);
return 0;
}
// 构建一个链表，并把头节点地址值返回
PNODE create_list(void)
{
int len;
int i;
int val; // 用来临时存放用户输入的节点的值
// 分配了一个不存放数据的头结点
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == NULL)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
// pTail始终执行的都是尾结点
PNODE pTail = pHead;
pTail->pNext = NULL;
printf("请输入你需要生成的链表节点的个数：\n");
scanf("%d" , &len);
for (i = 0; i < len; ++i)
{
printf("请输入第%d个节点的值:", i+1);
scanf("%d" , &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == NULL)
{
printf("分配失败，程序终止！\n");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
// 进行遍历
void traverse_list(PNODE pHead)
{
// 自定义一个指针用于遍历
PNODE p = pHead->pNext;
while(p != NULL){
printf("%d ",p->data );
p = p->pNext;
}
return;
}
// 判断链表是否为空
bool is_empty(PNODE pHead)
{
if (pHead->pNext == NULL)
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;
}
// 插入操作
// 在pHead所指向链表的第pos个节点的前面插入一个新的结点，该结点的值是val，pos从1开始
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;
return true;
}
// 删除操作
bool delete(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->pNext)
return false;
PNODE q = p->pNext;
*pval = q->data;
// 删除p结点后面的结点
p->pNext = p->pNext->pNext;
free(q);
q = NULL;
return true;
}
作者：山丘!
出处：http://www.cnblogs.com/mengd
-------------------------------------------
你闻讯而来，我大喜过望，我在这等你，你又在哪呢？喜欢的话加一个“关注”呗！
如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！https://www.cnblogs.com/mengd/p/11973677.html