c实现链表
目录
c实现链表
链表的结构定义：
链表的结构操作：
1、初始化链表
2、销毁链表
3、插入结点
4、输出链表数据
5、查找链表数据
扩展
代码实现
c实现链表
链表的结构定义：
/*** 链表结构定义 ***/ typedef struct Node {int data; //数据领struct Node * next; //指针域 }Node;链表的结构操作：
1、初始化链表
//1、初始化 Node * getNewNode(int val){Node * p = (Node *)malloc(sizeof(Node)); //为新链表开辟空间p->data = val; //数据域赋值p->next = NULL; //指针域指向空return p; }2、销毁链表
//2、销毁链表 void clear(Node * head){if(head == NULL) return ;//不能直接释放结点，如果直接释放会导致内存泄漏for(Node *p = head, *q; p; p = q){q = p->next;free(p);}return ; }3、插入结点
// //3.1、无头链表：插入节点 // Node *insert(Node *head, int pos, int val){ // if( pos == 0 ){ // //如果插入位置是0也就是头指针的位置 // //先将val值包成一个新节点，然后让新节点指向原来链表的首地址，再返回新链表的首地址 // Node *p = getNewNode(val); // p->next = head; // return p; // }// int n = -1; // for (Node *p = head; p; p = p->next) n += 1; // if(pos > n) pos = n;// //定义指针p找到待插入位置的前一个元素 // Node *p = head; // for (int i = 0; i < pos; i++) p = p->next; // Node * node = getNewNode(val); // 将val值包成一个新节点，插入节点 // node->next = p->next; // p->next = node; // return head; //返回新链表 // } //3.2 有头链表：插入节点 Node *insert2(Node *head, int pos, int val){// 虚拟头节点 指针p指向虚拟头节点 插入结点开辟新的空间Node new_head, *p = &new_head, *node = getNewNode(val);new_head.next = head;//虚拟头节点指向链表for (int i = 0; i < pos; i++) p = p->next;//找到插入前一个位置node->next = p->next;p->next = node;return new_head.next; //返回头结点的所指向链表的地址 }4、输出链表数据
//4、输出链表数据 void output_linklist(Node *head){int n = 0;// 先统计有多少个结点for (Node *p = head; p; p = p->next) n += 1; for (int i = 0; i < n; i++){printf("%3d",i);printf(" ");}printf("\n");for(Node *p = head; p; p = p->next){printf("%3d",p->data);printf("->");}printf("\n\n\n");return ; }5、查找链表数据
//5、查找 int find(Node *head, int val){Node *p = head;int n = 0;while (p){if(p->data == val){output_linklist(head);int len = n * (3 + 2) + 2;for (int i = 0; i < len; i++) printf(" ");printf("^\n");for (int i = 0; i < len; i++) printf(" ");printf("|\n");return 1;}n += 1;p = p->next;}return 0; }
扩展
while(~scanf("%d", &n)) 等价于 while(scanf("%d",&n)!=EOF)
EOF，为End Of File的缩写，通常在文本的最后存在此字符表示资料结束。EOF通常的值为-1。while(~scanf("%d", &n)) 意思就是当有值输入的时候，进入while，当没有值输入时就结束while。（输入了值，如果scanf成功读取了就返回1，取反的结果不为0，进入while；如果scanf没有成功读取，返回0，取反的结果不为0，进入while；如果没有输入，到达文件末尾则返回-1，取反的结果为0，结束while。）
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>/*** 链表结构定义 ***/
typedef struct Node
{int data; //数据领struct Node * next; //指针域
}Node;/*** 链表结构操作 ***/
//1、初始化
Node * getNewNode(int val){Node * p = (Node *)malloc(sizeof(Node)); //为新链表开辟空间p->data = val; //数据域赋值p->next = NULL; //指针域指向空return p;
}// //3.1、无头链表：插入节点
// Node *insert(Node *head, int pos, int val){
// if( pos == 0 ){
// //如果插入位置是0也就是头指针的位置
// //先将val值包成一个新节点，然后让新节点指向原来链表的首地址，再返回新链表的首地址
// Node *p = getNewNode(val);
// p->next = head;
// return p;
// }// int n = -1;
// for (Node *p = head; p; p = p->next) n += 1;
// if(pos > n) pos = n;// //定义指针p找到待插入位置的前一个元素
// Node *p = head;
// for (int i = 0; i < pos; i++) p = p->next;
// Node * node = getNewNode(val); // 将val值包成一个新节点，插入节点
// node->next = p->next;
// p->next = node;
// return head; //返回新链表
// }
//3.2 有头链表：插入节点
Node *insert2(Node *head, int pos, int val){// 虚拟头节点 指针p指向虚拟头节点 插入结点开辟新的空间Node new_head, *p = &new_head, *node = getNewNode(val);new_head.next = head;//虚拟头节点指向链表for (int i = 0; i < pos; i++) p = p->next;//找到插入前一个位置node->next = p->next;p->next = node;return new_head.next; //返回头结点的所指向链表的地址
}//2、销毁链表
void clear(Node * head){if(head == NULL) return ;//不能直接释放结点，如果直接释放会导致内存泄漏for(Node *p = head, *q; p; p = q){q = p->next;free(p);}return ;
}//4、输出链表数据
void output_linklist(Node *head){int n = 0;// 先统计有多少个结点for (Node *p = head; p; p = p->next) n += 1; for (int i = 0; i < n; i++){printf("%3d",i);printf(" ");}printf("\n");for(Node *p = head; p; p = p->next){printf("%3d",p->data);printf("->");}printf("\n\n\n");return ;
}//5、查找
int find(Node *head, int val){Node *p = head;int n = 0;while (p){if(p->data == val){output_linklist(head);int len = n * (3 + 2) + 2;for (int i = 0; i < len; i++) printf(" ");printf("^\n");for (int i = 0; i < len; i++) printf(" ");printf("|\n");return 1;}n += 1;p = p->next;}return 0;
}int main(void){srand(time(0));#define MAX_OP 7Node *head = NULL;for (int i = 0; i < MAX_OP; i++){int pos = rand() % (i+1), val = rand() % 100;printf("insert %d at %d to linklist.\n",val,pos);head = insert2(head,pos,val);output_linklist(head);}int val;while (~scanf("%d", &val)) {if (!find(head, val)) {printf("not found\n");}}clear(head);return 0;
}