1.链表的重要操作
我们知道，链表的基础单位是一个个节点，那么第一步便是创建节点。
struct node{typename data; //typename data 这里是数据域node* next ; //指针域 };
有一点要注意的是在C++中，是可以直接使用node的，而在C语言中，则需要使用struct node 不然会显示 unknown typename "node"
第二步，内存分配，关于内存的分配，主要有C语言中的malloc 函数和 c++ 中的new运算符
node* p = (node*) malloc(sizeof(node));//malloc，头文件是stdlib.h
但是老师更加推荐new，因为更加简洁方便
node*p = new node; 与内存分配对应的就是内存的释放
free(p); //c delete(p) ; //c++
注意它们的效果是释放了指针变量p所指的内存空间和将指针变量p指向空地址NULL，而p本身并没有消失
例1：求数组中n个元素，建立其线性链表结构
#include <iostream> #include <stdio.h> using namespace std; struct node{int data;node* next ; };struct node* Create_link(int a[],int n) {int i ;node *p,*pre,*head; //我们一般说知道一个节点的位置，那么这个指针一定是指向这个节点的前一个节点，故pre超级重要head = new node;head->next = NULL;pre = head;for(i=0;i<n;i++){p = new node;p->data = a[i];p->next =NULL;pre->next =p;pre=p;}return head; } int main() {int a[5]={1,2,3,4,5};node *p,*head ;head=Create_link(a,5);p=head->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}return 0; }
例2：在例1的基础上查找元素
int search_data(node* head,int x) {node* p =head->next ;int counter = 0 ;while(p!=NULL){if(p->data == x) counter++;p=p->next ;}return counter ; } int main() {int a[5]={1,4,4,4,5};node *head ;head=Create_link(a,5);printf("the number of x is %d",search_data(head,4));return 0; }
例3：插入元素
void insert_node(node* head ,int pos,int x) {node*p =head ;int i ;for(i=0;i<pos-1;i++)p=p->next ; //注意头节点没有数据，所以需要多next一次node *q = new node ;q->data = x;q->next =p->next ;p->next = q; } int main() {int a[5]={1,4,7,8,5};node *head,*p;head=Create_link(a,5);insert_node(head,3,100); //注意这里3是指第三个位置，那么插入之后第三个位置就是xp=head->next ;while(p!=NULL){printf("%d ",p->data);p=p->next;}return 0; }
例5：删除元素
void delect_data(node* head ,int x) {node* p =head->next ;node *pre =head ;while(p!=NULL){if(p->data ==x){pre->next =p->next ;delete(p);p = pre->next ;}else{p=p->next ;pre=pre->next ;}} } int main() {int a[5]={1,4,7,8,5};node *head,*p;head=Create_link(a,5);insert_node(head,3,100);p=head->next ;delect_data(head,100);while(p!=NULL){printf("%d ",p->data);p=p->next;}return 0; }
下面有一道较为完整的题目，来自
http://codeup.hustoj.com/problem.php?cid=100000607&pid=0
题目是：
#include <iostream> #include <stdio.h> #include<string> using namespace std; struct node{int data;node* next ; };struct node* Create_link(int a[],int n) {int i ;node *p,*pre,*head;head = new node;head->next = NULL;pre = head;for(i=0;i<n;i++){p = new node;p->data = a[i];p->next =NULL;pre->next =p;pre=p;}return head; } int search_data(node* head,int x) {node* p =head->next ;int counter = 0 ;while(p!=NULL){if(p->data == x) counter++;p=p->next ;}return counter ; } void insert_node(node* head ,int pos,int x) {node*p =head ;int i ;if(pos-1>0){for(i=0;i<pos-1;i++)p=p->next ;node *q = new node ;q->data = x;q->next =p->next ;p->next = q;cout<<"insert OK"<<endl;}else cout<<"insert fail"<<endl; } void delect_data(node* head ,int x) {node* p =head->next ;node *pre =head ;int flag = 0 ;if(head ==NULL){cout<<"Link list is empty"<<endl;}while(p!=NULL){if(p->data ==x){pre->next =p->next ;delete(p);p = pre->next ;flag = 1;}else{p=p->next ;pre=pre->next ;}}if(flag ==0) cout<<"delete fail"<<endl;if(flag == 1) cout<<"delete OK"<<endl; } int main() {int i,n,x,m,a,b,e;string act;node *head,*p,*q;head = new node ;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a);q = new node ;q->data = a ;q->next = head->next ;head->next = q;}scanf("%d",&m);for(i=0;i<m;i++){cin>>act;if(act=="get"){scanf("%d",&a);insert_node(head,a,1);}else if(act=="delect"){scanf("%d",&b);delect_data(head,b);}else if (act=="insert"){scanf("%d",&a);scanf("%d",&e);insert_node(head,e,a);}else if(act=="show"){p=head->next ;while(p!=NULL){printf("%d ",p->data);p=p->next;}}}return 0; }
