BSP Day60

#include 
#include 
//定义一个data结构体
typedef struct //一种数据类型
{
char name[32];
int id;
char addr[128];
}Tech_info;
//定义一个结点结构体
typedef struct node
{
Tech_info data; //数据域
struct node *next; //指针域
}Node;
int main()
{
//定义并初始化三个数据
Tech_info p1={"刘德华",1002,"香港"};
Tech_info p2={"郭德纲",1001,"天津"};
Tech_info p3={"王宝强",1003,"河北"};
//定义结点
Node *node1=(Node *)malloc(sizeof(Node));
if(node1==NULL)
{
printf("malloc failed\n");
}
Node *node2=(Node *)malloc(sizeof(Node));
if(node2==NULL)
{
printf("malloc failed\n");
}
Node *node3=(Node *)malloc(sizeof(Node));
if(node3==NULL)
{
printf("malloc failed\n");
}
//初始化结点数据域
node1->data=p1;
node2->data=p2;
node3->data=p3;
//初始化结点指针域，实现三个结点进行连接
node1->next=node2;
node2->next=node3;
node3->next=NULL;
printf("p3.name=%s\n",node1->next->next->data.name);
printf("p3.name=%s\n",node3->data.name);
return 0;
}

 ●单链表

● 双链表

■ 线性表的链式存储结构中 , 每个节点中包含两个指针域。

■ 指针域分别指向直接后继和直接前驱。

● 单向循环链表

■ 线性表的链式存储结构中 , 每个节点中只包含一个指针域。

■ 表中最后一个结点的 指针 域指向 头结点 ，整个链表形成一个环。

 概念解释

链表中的第一个结点 , 包含指向第一个数据元素的指针以及链表自身的一 - 些信息

■ 数据结点

链表中代表数据元素的结点 , 包含指向下一个数据元素的指针和数据元素的信息

■ 尾结点

链表中的最后一个数据结点 , 其下一元素指针为空 , 表示无后继。

 优点和缺点

➢ 优点 :

■ 无需一次性定制链表的容量

插入和删除操作无需移动数据元素

➢ 缺点 :

数据元素必须保存后继元素的位置信息

获取指定数据的元素操作需要顺序访问之前的元素

链表和数组

链表和数组 一样 , 可以用于存储一系列的元素 , 但是链表和数组的实现机制完全不同。

数组：

        要存储多个元素，数组（或列表）可能是最常用的数据结构。

        几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便，提供了一个便利的 []         语法来访问它的元素。

但是数组也有很多缺点 :

        数组的创建通常需要申请一段连续的内存空间( 一整块的内存 ), 并且大小是固定的 ( 大多数编程

        语言数组都是固定的), 所以当当前数组不能满足容量需求时 , 需要扩容 . ( 一般情况下是申请一

        个更大的数组, 比如 2 倍 . 然后将原数组中的元素复制过去 )

        而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的移动。

链表：

        要存储多个元素, 另外一个选择就是使用链表。

        但不同于数组, 链表中的元素在内存中不必是连续的空间。

        链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的指针组成。

相对于数组 , 链表有一些优点 :

        内存空间不必连续的. 可以充分利用计算机的内存 . 实现灵活的内存动态管理。

        链表不必在创建时就确定大小, 并且大小可以无限的延伸下去。

        链表在插入和删除数据时, 相对数组效率高很多。

相对于数组 , 链表有一些缺点 :

        链表访问任何一个位置的元素时, 都需要从头开始访问 .( 无法跳过第一个元素访问任何一个元

        素) 。

        无法通过下标直接访问元素, 需要从头一个个访问 , 直到找到对应的位置。

单向链表设计

例程：创建一个动态单向链表

1. 定义链表结点：数据域 + 指针域

2. 定义链表结构体：头结点指针 + 结点数

3. 初始化链表

4. 指定位置插入新数据

5. 删除指定位置数据

6. 获取链表长度

7. 依据数据查找所在链表位置

8. 返回第一个结点

9. 打印链表结点数据

10. 释放链表

例程：动态例程 linklist.c 、 linklist.h 、 main.c

添加结点

 删除结点

 linklist.c：实现链表的创建、插入、删除、查找、获取链表长度、释放操作

#include "linklist.h"
//初始链表
LinkList *init_linklist(void)
{
LinkList *list=(LinkList *)malloc(sizeof(LinkList));
list->size=0;
//头结点
list->head=(LinkNode *)malloc(sizeof(LinkNode));
list->head->data=NULL;
list->head->next=NULL;
return list;
}
//指定位置插入,z
void insert_linklist(LinkList *list, int pos, void *data)
{
int count;
if(list == NULL)
{
return ;
}
if(data == NULL)
{
return ;
}
if(pos<0 || pos >list->size)
{
pos=list->size;
}
//创建新的结点
LinkNode *newnode=(LinkNode *)malloc(sizeof(LinkNode));
newnode->data=data;
newnode->next=NULL;
//找结点
//辅助指针变量
LinkNode *pcurrent=list->head;
int i;
for(i=0;i
{
pcurrent=pcurrent->next;
}
#if 0
while(pcurrent!=NULL&&pcurrent->next!=NULL)
{
pcurrent=pcurrent->next;
count++;
if(count=pos)
{
break;
}
}
#endif
//新结点插入链表
newnode->next=pcurrent->next;
pcurrent->next=newnode;
list->size++;
}
//删除指定位置的值
void del_by_pos_linklist(LinkList *list, int pos)
{
if(list == NULL)
{
return ;
}
if(pos<0 || pos >list->size)
{
return ;
}
//找结点
//辅助指针变量
LinkNode *pcurrent=list->head;
int i;
for(i=0;i
{
pcurrent=pcurrent->next;
}
//删除结点
LinkNode *delnode=pcurrent->next;
pcurrent->next=delnode->next;
free(delnode);
list->size--;
}
//获取链表长度
int size_linklist(LinkList *list)
{
return list->size;
}
//查找
int find_linklist(LinkList *list, void *data)
{
if(list == NULL)
{
return -1;
}
if(data == NULL)
{
return -2;
}
//遍历查找
LinkNode *pcurrent = list->head->next;
int i=1;
while(pcurrent!=NULL)
{
if(pcurrent->data==data)
{
break;
}
i++;
pcurrent=pcurrent->next;
}
return i;
}
//返回第一个结点
void *first_linklist(LinkList *list)
{
return list->head->next->data;
}
//打印链表结点
void print_linklist(LinkList *list, printlinknode print)
{
if(list == NULL)
{
return ;
}
//辅助指针变量
LinkNode *pcurrent=list->head->next;
while(pcurrent!=NULL)
{
print(pcurrent->data);
pcurrent=pcurrent->next;
}
}
//释放链表内存
void free_linklist(LinkList *list)
{
if(list == NULL)
{
return ;
}
//辅助指针变量
LinkNode *pcurrent=list->head;
while(pcurrent!=NULL)
{
//缓存下一个结点
LinkNode *pnext=pcurrent->next;
free(pcurrent);
pcurrent=pnext;
}
//释放链表内存
list->size=0;
free(list);
}

#ifndef LINKLIST_H
#define LINKLIST_H
#include 
#include 
#include 
//链表节点
typedef struct NODE
{
void *data;
struct NODE *next;
}LinkNode;
//链表结构体
typedef struct
{
LinkNode *head;
int size;
}LinkList;
//打印函数指针
typedef void (*printlinknode)(void *);
//初始链表
LinkList *init_linklist(void);
//指定位置插入
void insert_linklist(LinkList *list, int pos, void *data);
//删除指定位置的值
void del_by_pos_linklist(LinkList *list, int pos);
//获取链表长度
int size_linklist(LinkList *list);
//依据数据查找所在位置
int find_linklist(LinkList *list, void *data);
//返回第一个结点
void *first_linklist(LinkList *list);
//打印链表结点
void print_linklist(LinkList *list, printlinknode print);
//释放链表内存
void free_linklist(LinkList *list);
#endif

#include "linklist.h"
typedef struct
{
char name[64];
int age;
int score;
}Person;
//打印函数
void my_print(void *data)
{
Person *p=(Person *)data;
printf("name:%s age:%d score:%d\n",p->name,p->age,p->score);
}
int main()
{
//创建链表
LinkList *list=init_linklist();
//获取链表长度
printf("list 长度：%d\n",size_linklist(list));
//创建数据
Person p1={"大明",18,96};
Person p2={"小明",19,97};
Person p3={"老明",20,98};
//数据插入链表
insert_linklist(list, 0, &p1);//0表示头插法
insert_linklist(list, 0, &p2);
//打印
print_linklist(list, my_print);
printf("\n");
//指定位置1处，插入
insert_linklist(list, 1, &p3);
//打印
print_linklist(list, my_print);
printf("\n");
//依据数据找所在位置
int ret=find_linklist(list, &p3);
printf("\"老明\"所在位置：%d\n",ret);
//指定位置1处，删除
del_by_pos_linklist(list, 1);
//打印
print_linklist(list, my_print);
printf("\n");
//获取链表长度
printf("list 长度：%d\n",size_linklist(list));
//返回第一个结点
Person *p=(Person *)first_linklist(list);
printf("第一个结点：name-%s,age-%d,score-%d\n",p->name,p->age,p->score);
//销毁
free_linklist(list);
return 0;
}