| 【C语言】 | 您所在的位置：网站首页 › c语言链表的建立和输出的区别 › 【C语言】 |
【C语言】
|
更新中 文章目录 单链表单链表的基础操作定义结点初始化初始化单链表时为什么要用到二级指针？ 求当前元素个数插入结点头插法&尾插法删除结点取元素创建单链表访问单链表摧毁单链表清空单链表清空链表和销毁链表的区别： 实践：带头结点的循环单链表 双向循环链表结构体定义初始化插入元素删除结点求当前元素个数撤销内存空间 链式堆栈疑问&补充关于什么时候用“->”什么时候用“.”*p、p，&p的区别结构体相关利用头插法逆置链表 单链表 单链表的基础操作 定义结点 typedef struct node// { int data;//data域用于存放元素 struct node* next;//next域用于存放指向下一个结点的指针 }Node;//Node=struct node 初始化 //初始化单链表 void ListInitiate(Node** head) { *head = (Node*)malloc(sizeof(Node));//申请头结点，由head指示其地址 //c++:*head=new Node if (*head == NULL)//检验是否申请成功 { printf("error"); return; } (*head)->next = NULL;//置结束标记NULL } 初始化单链表时为什么要用到二级指针？在初始化过程中，需要修改头指针，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。 如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。 在使用带头结点的单链表时 1、初始化链表头部指针需要用二级指针 2、销毁链表需要用到二级指针 3、插入、删除、遍历、清空结点用一级指针即可 注意： 如果是不带头结点的单链表，插入、删除和清空结点也需要二级指针（比如往空链表中插入一个节点时，新插入的节点就是链表的头指针，此时会改动头指针。同理，删除第一个结点和清空结点都会改动头指针）。 来源：单链表中什么时候使用二级指针 求当前元素个数 //求当前元素个数 int ListLength(Node* head) { Node* p = head; //p指向头结点 int size = 0; while (p->next != NULL)//循环计数 { p = p->next; size++; } return size; } 插入结点 //插入结点 int ListInsert(Node* head, int i, int x)//dataType x { //在带头结点的饭链表head的第i个结点前插入一个存放元素x的结点 //插入成功返回1，否则为0 Node* p, * q; int j; p = head;//p指向头结点 j = -1; while (p->next != NULL && j printf("插入位置出错！"); return 0; } q = (Node*)malloc(sizeof(Node));//生成新结点 if (q == NULL) { printf("error"); return 0; } q->data = x;//新结点数据域赋值 q->next = p->next;//插入步骤一 p->next = q;//插入步骤二（步骤不可颠倒！ return 1; } 头插法&尾插法 //头插法创建链表 void headCreate(Node*head,int n) { Node* newNode; while (n--) { newNode = (Node*)malloc(sizeof(Node)); scanf_s("%d", &newNode->data); // 主要核心，新节点指向头指针的next，头指针指向新节点。 newNode->next = head->next; head->next = newNode; } } //尾插法创建链表 void rearCreate(Node* head,int n) { Node *p, *newNode; p = head; while (n--) { newNode = (Node*)malloc(sizeof(Node)); scanf("%d", &newNode->data); // 新节点指向p的next，p的nex指向新节点，p指向新节点。 newNode->next = p->next; p->next = newNode; p = p->next; } } 删除结点 //删除 int ListDelete(Node* head, int i, int* x) { //删除带头结点单链表head的第i个结点 //删除结点的数据域由x带回，删除成功返回1，否则为0 Node* p, * s; int j; p = head; j = -1; while (p->next != NULL && p->next->next != NULL && j printf("插入位置出错！"); return 0; } s = p->next;//指针s指向第i个结点 *x = s->data;//把指针s所指向的数据域赋予x p->next = p->next->next;//删除结点 free(s); return 1; } 取元素 //取元素 int ListGet(Node* head, int i, int *x) { Node* p; int j; p = head; j = -1; while (p->next != NULL && j printf("取元素位置出错"); return 0; } *x = p->data; return 1; }p不申请动态内存的原因： p在函数内的生存期就能满足需求，没有必要malloc一个新结点。 （动态分配内存后，p生存期的结束取决于我们何时手动删除（free/delete）它。） 创建单链表 void Creat(Node* head,int n)//创建链表 { Node* p = head; for(int i= 0;i return; } scanf("%c", &New->data); p->next = New;//将New链接至链表尾部 p = p->next;//后移p至新链表尾部 } p->next = NULL; } 访问单链表 void visit(Node* list)//访问链表 { if (list->next == NULL)//当链表只剩头指针时 printf("The content of list:null"); else { printf("The content of list:"); for (Node* p = list->next; p != NULL; p = p->next)//遍历链表 { printf("%c", p->c); } printf("\n"); } } 摧毁单链表 void DestroyList(Node* head) { Node * p; if (head == NULL) return ; while (head) { p = head->next; free(head); head = p; } return ; } 清空单链表 void destory(Node* head)//清空链表（注意!清空与销毁概念不同！！） { Node* p;//定义一个指针 while (head->next != NULL) { p = head->next;//使p指向list的next head->next = p->next;//再让list存住下一个p free(p);//释放p } /*另一种清空方法： Node *p,*q; p=head->next while(p!=NULL) { q=p->next; free(p); p=q; } head->next=NULL; */ } 清空链表和销毁链表的区别： 清空链表：将所有除头节点以外的存放有数据的节点释放掉销毁链表：将包括头结点在内的所有节点释放掉注意：当清空所有有数据的节点，并且释放头结点后，该链表就无法再通过头结点创建，访问，插入，删除节点，因此相当于销毁了此链表 实践：带头结点的循环单链表 #include #include #include"List.h"//上文提到的函数均写在头文件List.h中 int main() { int n = 0, num= 0,x; Node* head; ListInitiate(&head); printf("输入链表结点数\n"); scanf("%d", &n); Creat(head,n); printf("输入插入位置（第i个）\n"); scanf("%d",&x); printf("输入插入的数字\n"); scanf("%d", &num); ListInsert(head, x-1, num); Visit(head); Destory(&head); return 0; }创建带头结点的循环链表的操作方法和带头结点的链表的操作方法类同 差别为： （1）在初始化函数中把(*head)->next = NULL;改为(*head)->next = *head; （2）在其他函数中把p->next != NULL和p->next->next != NULL中的NULL改为head 双向循环链表 结构体定义 typedef struct node { int data;//不一定为int，可以是其他类型（DataType struct node* prior; struct node*next; }DLNode; 初始化 void Initstiate(DLNode**head) { *head = (DLNode*)malloc(sizeof(DLNode)); (*head)->prior=*head;//构成前驱指针循环链表 (*head)->next=*head;//构成后继指针循环链表 } 插入元素 //插入结点 int Insert(DLNode* head, int i, int x)//dataType x { //在带头结点的饭链表head的第i个结点前插入一个存放元素x的结点 //插入成功返回1，否则为0 //与单链表操作类似 DLNode* p, * s; int j; p = head;//p指向头结点 j = -1; while (p->next != NULL && j printf("插入位置出错！"); return 0; } s = (Node*)malloc(sizeof(Node)); if (s == NULL)//检验是否成功申请动态内存 { printf("error q"); return 0; } s->data = x; //以下差别较大 s->prior=p->prior;//step1 p->prior->next=s;//step2 s->next=p;//step3 p->prior=s;//step4 return 1; }
|
注意：①②和③④不可颠倒，步骤①和②之间可颠倒，③和④之间可颠倒。
【本文地址】
公司简介
联系我们