14°

数据结构入门-离散存储(链表)

一、预备知识:typedef

基本使用

#include <stdio.h>

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 = &amp;st;  // 等价于 ST * ps = &amp;st;


ST st2;
st2.sid = 10;

printf("%d \n", st2.sid);

return 0;

}

也可以这样使用,这样更加的方便

#include <stdio.h>

typedef struct Student { int sid; char name[100]; char sex; }* PST; // PST等价于 typedef struct *

int main(void) { struct Student st; PST ps = &st;

ps-&gt;sid = 99;
printf("%d\n", ps-&gt;sid);

return 0;

}

还可以把上面的两个结合起来

#include <stdio.h>

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-&gt;sid = 99;
printf("%d\n", ps-&gt;sid);

return 0;

}

二、离散存储(链表)

定义:n个节点离散分配,彼此通过指针相连,每一个节点只有一个前驱节点和一个后续节点,首节点没有前驱节点,尾节点没有后续节点

专业术语:

  1. 首节点:第一个有效节点
  2. 尾节点:最后一个有效节点
  3. 头节点:首节点前面
  4. 头指针:指向头节点的指针变量
  5. 尾指针:指向尾节点的指针变量

注意:头节点的数据类型和首节点类型一样,头节点里面没有存放有效数据,没有实际含义,为了方便对链表的操作

如果通过希望一个函数来对链表进行处理,我们至少需要接收链表的那些参数

只需要一个参数:头指针

因为我们可以通过头指针推算出链表的其他所有参数

每一个链表节点的数据类型如何表示

#include <stdio.h>

typedef struct Node { int data; // 数据域 struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点 }NODE , *PNODE; // NODE 等价于struct Node // PNODE 等价于struct Node *

int main(void) { return 0; }

分类:

  1. 单链表
  2. 双链表:每一个节点有两个指针域
  3. 循环链表:能通任何一个节点找到其他所有的节点
  4. 非循环链表

算法:

  1. 遍历
  2. 查找
  3. 清空
  4. 销毁
  5. 求长度
  6. 排序
  7. 删除节点
  8. 插入节点

算法

狭义的算法是与数据的存储方式密切相关

广义的算法与数据的存储方式无关

泛型

利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的

多敲代码,熟练的掌握,并进行改进

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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 , &amp;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-&gt;pNext = NULL;


printf("请输入你需要生成的链表节点的个数:\n");
scanf("%d" , &amp;len);

for (i = 0; i &lt; len; ++i)
{
    printf("请输入第%d个节点的值:", i+1);
    scanf("%d" , &amp;val);

    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (pNew == NULL)
    {
        printf("分配失败,程序终止!\n");
        exit(-1);
    }

    pNew-&gt;data = val;
    pTail-&gt;pNext = pNew;
    pNew-&gt;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-&gt;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-&gt;pNext; i &lt; len -1; ++i , p = p-&gt;pNext)
{
    for (j = i+1 , q = p-&gt;pNext; j &lt; len; ++j , q = q-&gt;pNext)
    {
        if (p-&gt;data &gt; q-&gt;data)
        {
            t = p-&gt;data;
            p-&gt;data = q-&gt;data;
            q-&gt;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 &amp;&amp; i &lt; pos-1)
{
    p = p-&gt;pNext;
    ++i;
}

if (i &gt; pos-1 || NULL == p)
    return false;


PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
    printf("动态分配内存失败\n");
    exit(-1);
}
pNew-&gt;data = val;
PNODE q = p-&gt;pNext;
p-&gt;pNext = pNew;
pNew-&gt;pNext = q;

return true;

}

// 删除操作 bool delete(PNODE pHead , int pos, int * pval) {

int i = 0;
PNODE p = pHead;

while(NULL != p-&gt;pNext &amp;&amp; i &lt; pos-1)
{
    p = p-&gt;pNext;
    ++i;
}

if (i &gt; pos-1 || NULL == p-&gt;pNext)
    return false;



PNODE q = p-&gt;pNext;
*pval = q-&gt;data;

// 删除p结点后面的结点
p-&gt;pNext = p-&gt;pNext-&gt;pNext;
free(q);
q = NULL;

return true;

}

本文转载自博客园,原文链接:https://www.cnblogs.com/mengd/p/11973677.html

全部评论: 0

    我有话说: