1.1 动态链表的实现
以无头链表的形式实现
struct Node
{
char name[15];
int num;
char sex[3];
struct Node*next;
};
1.1.1 创建链表
//第一个节点
struct Node *p = (struct Node*)malloc(sizeof(struct Node));
scanf(p);
p->next = NULL
//第二个节点
struct Node *pf = (struct Node*)malloc(sizeof(struct Node));
scanf(pf);
pf->next = NULL
p->next = pf;
//第三个节点
struct Node *pt = (struct Node*)malloc(sizeof(struct Node));
scanf(pt);
pt->next = NULL
写一个子函数，子函数的返回表头指针
struct Node * creatLink()
{
struct Node *head //链表的表头指针
struct Node *pf; //原来链表的最后一个节点的指针
struct Node *pNew; //每次新申请的节点的指针
int n; //节点的个数，用户选择输入的数据的个数
int i;
for(i = 1; i<= n; i++
{
//新申请一块内存空间
pNew = (struct Node*)malloc(sizeof(struct Node));
//新申请的节点的指针域置空
//存储数据，再新申请的空间中
scanf
如果新申请的节点是第一个节点
链表的表头指针指向第一个节点
链表的表尾指针指向第一个节点 （第一个节点既是表头也是表尾）
如果申请的不是第一个节点
原来链表的最后一个节点的指针域存储新申请的节点的地址
新申请的节点成为链表的最后一个节点（表尾）
}
返回表头指针
}
1.1.2 俩链表的遍历
知道链表的表头，从链表的表头开始依次往下遍历，需要知道遍历到什么时候停止
1.1.3 链表节点的查找
查找：静态查找------>查找查找表中的数据，不修改查找
动态查找---->需要对查找表进行写操作，修改原来的数据
关键字：查找的条件
主关键字：学号，要么找到一个人，要么没有
次关键字：符合该条件可以有多个数据
1.1.4 链表节点的删除
首先找到结点------------->删除操作---->删除之后链表仍然有序
没有找到结点------------->删除失败
pf; //表示要删除的结点
判断pf的位置：
表头 pf == head
中间
表尾 pf->next == NULL
1) 在表尾插入
2) 按照某种(某一个数据项)顺序插入
按照编号从小到大的形式进行插入
pNew; //要插入的新结点
pf //新节点要插入的位置 新节点插入在pf的前面
//查找要插入的位置
满足条件： pNew->num < pf->num
新节点pNew插入在pf的前面
//插入的位置的判断
判断pf的位置
1） pf == head; //新节点成为新的表头
2） pf在中间。 //新节点pNew插入在pf的前面
3） 链表中没有合适的要插入，插入到链表的最后， pf == NULL
#include <stdio.h> #include <stdlib.h> typedef struct Node { char name[15]; int num; char sex[3]; struct Node*next; }LinkNode,*pLinkNode;
LinkNode *creatLink(int n); void printLink(const LinkNode *phead); void findLinkNode(LinkNode *phead); LinkNode *findLinkNodeName(LinkNode *phead,char *name,LinkNode **pt); LinkNode *findLinkNodeNum(LinkNode *phead,int num,LinkNode **pt); LinkNode *insertLinkNode(LinkNode *phead); LinkNode *deleteLinkNode(LinkNode *phead);
int main() { LinkNode *head; int n;
printf("请输入节点的个数："); scanf("%d",&n);
head = creatLink(n);
printLink(head);
while(1) { //findLinkNode(head); head = insertLinkNode(head); printLink(head);
head = deleteLinkNode(head); printLink(head); }
return 0; }
/*********************************************************** *函数原型：LinkNode *creatLink(int n) *函数功能：创建链表 *函数参数：int n; //表示链表节点的个数 *函数返回值：返回链表的表头，如果为NULL，创建失败 ************************************************************/
LinkNode *creatLink(int n) { int i; LinkNode *head = NULL; //链表的表头指针 LinkNode *pf = NULL; //链表的表尾指针(指针链表的最后一个节点) LinkNode *pNew = NULL; //新申请的节点的指针
for(i = 1; i <= n; i++) { //新申请一个节点 pNew = (LinkNode *)malloc(sizeof(LinkNode)); //新申请的节点的指针域为空 pNew->next = NULL; //往新申请的节点存储数据 printf("请输入%d个节点的姓名 编号 性别：",i); scanf("%s %d %s",pNew->name,&pNew->num,pNew->sex); if(i == 1) //判断是否为申请的第一个节点 { head = pNew;//表头指针指向新申请的节点 pf = pNew; //表尾指针指向新申请的节点 } else { pf->next = pNew; //新申请的节点的地址存储在原来链表的最后一个结点的指针域 pf = pNew; //新申请的结点称为链表新的表尾 } } return head; }
/*********************************************************** *函数原型：void printLink(const LinkNode *phead) *函数功能：链表的遍历 *函数参数：const LinkNode *phead 链表的表头指针 *函数返回值：无 *说明： 链表的最后一个结点的指针域为NULL ************************************************************/ void printLink(const LinkNode *phead) { if(phead == NULL) { return; } printf("姓名\t 编号\t 性别\n"); while(phead != NULL) { printf("%s\t %d\t %s\n",phead->name,phead->num,phead->sex); phead = phead->next; } }
/*********************************************************** *函数原型：LinkNode *findLinkNodeNum(LinkNode *phead, int num LinkNode **pt) *函数功能：查找链表中的某一个结点 *函数参数：LinkNode *phead 链表的表头 int num 查找的条件 LinkNode **pt 将查找的节点的一个节点的地址保存在*pt *函数返回值：查找到的节点的地址 如果没有找到则返回NULL ************************************************************/ LinkNode *findLinkNodeNum(LinkNode *phead,int num,LinkNode **pt) {
while(phead != NULL ) { if(num < phead->num) { return phead; } *pt = phead; phead = phead->next; }
return NULL; }
/*********************************************************** *函数原型：LinkNode *findLinkNodeName(LinkNode *phead, char *name, LinkNode **pt) *函数功能：查找链表中的某一个结点 *函数参数：LinkNode *phead 链表的表头 char *name 查找的条件 LinkNode **pt 将查找的节点的一个节点的地址保存在*pt *函数返回值：查找到的节点的地址 如果没有找到则返回NULL ************************************************************/ LinkNode *findLinkNodeName(LinkNode *phead,char *name,LinkNode **pt) {
while(phead != NULL ) { if(str_cmp(phead->name,name) == 1) { return phead; } *pt = phead; phead = phead->next; }
return NULL; }
int str_cmp(const char *str,const char *buf) { while(*str != '\0' || *buf != '\0') { if(*str != *buf) { return 0; } str++; buf++; } return 1; }
/*********************************************************** *函数原型：void findLinkNode(LinkNode *phead) *函数功能：查找链表中的某一个结点 *函数参数：LinkNode *phead 链表的表头 *函数返回值：无 ************************************************************/
void findLinkNode(LinkNode *phead) { int num;
printf("请输入要查找的编号："); scanf("%d",&num);
while(phead != NULL) { if(phead->num == num) { printf("============查找成功==============\n"); printf("姓名\t 编号\t 性别\n"); printf("%s\t %d\t %s\n",phead->name,phead->num,phead->sex); break; //return pehad; } phead = phead->next; } if(phead == NULL) { printf("===============查找失败============\n"); } }
//void findLinkNode(LinkNode *phead) //{ // //查找的条件 // int flag; // printf("1: 按照姓名查找"); // printf("2: 按照编号查找"); // printf("2: 按照成绩范围查找"); // // switch(flag) // { // case 1: // case 2: // case 3: // case 4: // } // //}
/*********************************************************** *函数原型：LinkNode *deleteLinkNode(LinkNode *phead) *函数功能：删除链表中的一个结点 *函数参数：LinkNode *phead 链表的表头 *函数返回值：返回链表的表头， ************************************************************/ LinkNode *deleteLinkNode(LinkNode *phead) { LinkNode *pf = NULL; //要删除的结点 LinkNode *pt = NULL; //要删除的结点的前一个结点 char buf[15];
printf("请输入要删除的姓名："); scanf("%s",buf);
pf = findLinkNodeName(phead,buf,&pt); if(pf == NULL) { printf("删除失败\n"); return phead; } if(pf == phead) //删除表头 { phead = phead->next; //表头的下一个结点称为新的表头 } else //删除中间 或者 删除的是表尾 { pt->next = pf->next;//要删除的结点的前一个结点的指针域存储 //要删除的结点的一个结点的地址 } free(pf); //删除pf指针指向的结点 pf = NULL;
return phead; } /*********************************************************** *函数原型：LinkNode *deleteLinkNode(LinkNode *phead) *函数功能：在链表中的某一个结点 *函数参数：LinkNode *phead 链表的表头 *函数返回值：返回链表的表头， ************************************************************/ LinkNode *insertLinkNode(LinkNode *phead) { LinkNode *pf = NULL; //要插入的结点位置 LinkNode *pt = NULL; //要插入的结点的前一个结点 LinkNode *pNew = NULL; //新插入的结点
printf("请输入要插入的姓名 编号 性别："); pNew = (LinkNode *)malloc(sizeof(LinkNode)); scanf("%s %d %s",pNew->name,&pNew->num,pNew->sex);
pf = findLinkNodeNum(phead,pNew->num,&pt); if(pf == NULL) { //新节点只能插入在表尾 pt->next = pNew; pNew->next = NULL; //新节点成为新的表尾 } if(pf == phead) //插在表头前面成为新的表头 { pNew->next = phead; phead = pNew; } else //插入中间 { pt->next = pNew; //要插入的结点的前一个结点的指针域存储新申请的结点的地址 pNew->next = pf; //新申请的结点的指针域存储要插入的结点的地址 } return phead; } |