1.2链表 

定义：

• 用一组任意的存储单元存储线性表中的数据元素。

特点：

• 相比顺序存储结构，链式存储结构中，除了需要存储数据元素信息之外，还需要存储它的后继元素的存储地址(指针)。
• 单链表结点的物理位置不一定连续，单链表逻辑上通过指针实现连续。
• 单链表有一个头结点和一个尾结点，并且只有尾结点没有后继结点，其他结点有且仅有一个后继结点。
• 只要知道了链表的头结点，就可以遍历整个链表。
   

​

• 单链表的每一个结点包含两部分：数据域和指针域。
• 表头：用来存放第一个结点的地址。
• 表尾：表尾没有后继，所以尾结点的指针域为空指针（NULL）。

 实现：

• c语言定义：

typedef struct node{int data;//数据域 node * next;//指针域 
}LNode,*LinkList;//LinkList是指向LNode类型数据的指针类型定义 

• LinkList是指向LNode类型数据的指针类型定义 ，也就是说，在定义一个指向LNode类型数据的指针变量时，语句

LNode *L;

和

LinkList L;

是等价的。

• c++定义：

class ListNode{public:		ListNode * next;int data;
};
class LinkList
{
public:LinkList(){node=new ListNode;node->next=NULL;}~LinkList(){delete node;}void CreateLinkListBack(int n);void CreateLinkListHead(int n);void InsertNode(int position,int elem);void removeNode(ListNode* p); ListNode* findNode(int value);void PrintLinkList();
public:ListNode *node;
};

基本操作：

• 初始化链表

//初始化链表 
LinkList init_list() 
{LinkList L=new LNode;if(!L)return NULL;L->next=NULL;//指针域置空 return L;	
}

• 打印链表

//打印链表
void Printf_list(LinkList &L)
{LinkList temp=L->next;while(temp!=NULL){cout<data<<"->";temp=temp->next;}} 

•  插入数据（头插）

步骤：

1. 先创建一个新节点s(LinkList),并给数据域赋值，
2. 新节点的指针域指向L-next,
3. L的指针域next指向s。

​

//插入数据（头插）
void create_LinkList(LinkList &L,int n)
{	while(n--){LinkList s=new LNode;cin>>s->data;s->next=L->next;L->next=s;	} 		
} 

注意：使用头插法插入数据后，链表中数据的顺序和插入前的数据顺序相反。 

• 插入数据（尾插）

步骤：

1. 先让r节点指向尾结点，
2. 创建一个新节点s(LinkList),并给数据域赋值，且s->next为NULL，因为s为尾结点，
3. r的指针域指向s,
4. 更新尾节点，即r=s。

​

//插入数据（尾插）
void create_LinkList_back(LinkList &L,int n)
{LinkList r=L;while(n--){LinkList s=new LNode;cin>>s->data;s->next=NULL;r->next=s;r=s;}} 

 注意：使用尾插法插入数据后，链表中数据的顺序和插入前的数据顺序相同。 

• 在指定位置插入数据

 //插入数据
void InsertList(LinkList q,int e)
{LinkList p=new LNode;p->data=e;p->next=q->next;q->next=p;}

• 查找相应数据

LinkList Get_elem(LinkList &L,int e)
{LinkList temp=L->next;while(temp!=NULL){if(e==temp->data){return temp;}temp=temp->next;		}return NULL;} 

完整程序

#include using namespace std;typedef struct node{int data;//数据域 struct node * next;//指针域 
}LNode,*LinkList;//LinkList是指向LNode类型数据的指针类型定义 //初始化链表 
LinkList init_list()//引用 
{LinkList L=new LNode;if(!L)return NULL;L->next=NULL;//指针域置空 return L;	
}
//插入数据（头插）
void create_LinkList(LinkList &L,int n)
{	while(n--){LinkList s=new LNode;cin>>s->data;s->next=L->next;L->next=s;	} 		
} 
//插入数据（尾插）
void create_LinkList_back(LinkList &L,int n)
{LinkList r=L;while(n--){LinkList s=new LNode;cin>>s->data;s->next=NULL;r->next=s;r=s;}} 
//打印链表
void Printf_list(LinkList &L)
{LinkList temp=L->next;while(temp!=NULL){cout<data<<"->";temp=temp->next;}cout<data=e;p->next=q->next;q->next=p;}
LinkList Get_elem(LinkList &L,int e)
{LinkList temp=L->next;while(temp!=NULL){if(e==temp->data){return temp;}temp=temp->next;		}return NULL;} 
int main()
{LinkList L=init_list();if(!L){cout<<"初始化失败"<>num;create_LinkList_back(L,num);	Printf_list(L);	int elem;LinkList elem_list;cout<<"请输入需要查找的数"<>elem;elem_list=Get_elem(L,elem);while(!elem_list) {cout<<"没有查找到，请重新输入"<>elem; elem_list=Get_elem(L,elem);}cout<<"找到相应数据，数据地址为："<>elem_insert; 	InsertList(elem_list,elem_insert); Printf_list(L);} return 0;
}

c++版本：

#include 
using namespace std;
class ListNode{public:		ListNode * next;int data;
};
class LinkList
{
public:LinkList(){node=new ListNode;node->next=NULL;}~LinkList(){delete node;}void CreateLinkListBack(int n);void CreateLinkListHead(int n);void InsertNode(int position,int elem);void removeNode(ListNode* p); ListNode* findNode(int value);void PrintLinkList();
public:ListNode *node;
};
//头插 
void LinkList::CreateLinkListHead(int n)
{while(n--){//插入的数据 ListNode* l=new ListNode;cin>>l->data;l->next=node->next;node->next=l;}
}
//尾插 
void LinkList::CreateLinkListBack(int n)
{ListNode* r=node;while(n--){ListNode* l=new ListNode;cin>>l->data;l->next=NULL;r->next=l;r=l;}}
//在第i个位置插入元素 
void LinkList::InsertNode(int position,int elem)
{int j;ListNode* p=node->next;for(j=1;jnext;if(p==NULL)break;}if(p==NULL &&j<(position-1))return ;
//	while(p)
//	{
//		j++;
//		if(j==position)
//			break;
//		p=p->next;
//	}ListNode* q=new ListNode;q->data=elem;q->next=p->next;p->next=q;
}
//移除节点 
void LinkList::removeNode(ListNode* p)
{if(p==NULL)return;ListNode* temp=node;while(temp->next!=p){temp=temp->next;		}temp->next=p->next;delete p;
}
//寻找某节点 
ListNode* LinkList::findNode(int value)
{ListNode* temp=node->next;while(temp){if(temp->data==value)return temp;temp=temp->next;}return NULL;}
//打印链表 
void LinkList::PrintLinkList()
{ListNode* temp=node->next;while(temp){cout<data<<"->";temp=temp->next;}std::cout<

typedef struct SqStack_dynamic{int* base;//栈底 int* top;//栈顶 
}SqStack_dynamic;

typedef struct SqStack_static{int data[Maxsize];int top;//栈顶 
}SqStack_static;

class stack_static{public:stack_static(){MaxSize=10;top=0;	data= new int[MaxSize];				}void push(int e);void pop(int &e);void GetTop(int &e);private:int MaxSize;int top;int *data;
};

void InitStack(SqStack_dynamic &stack)
{stack.base= new int[Maxsize];stack.top=stack.base;
}

void push(SqStack_dynamic &stack,int e)
{if((stack.top-stack.base)>=Maxsize)return;*stack.top=e;stack.top++;
}

void stack_static::push(int e)
{data[top]=e;top++;
}

void pop(SqStack_dynamic &stack,int &e)
{if(stack.base==stack.top)return;stack.top--;e=*stack.top;	
}

void stack_static::pop(int &e)
{top--;e=data[top];
}

int GetTop(SqStack_dynamic &stack)
{if(stack.base!=stack.top)return *(stack.top-1);elsereturn -1;
}

void stack_static::GetTop(int &e)
{if(top!=MaxSize)e=data[top-1];elsee=-1;
}

#include
using namespace std;
#define Maxsize 100
typedef struct SqStack_dynamic{int* base;//栈底 int* top;//栈顶 
}SqStack_dynamic;class stack_static{public:stack_static(){MaxSize=10;top=0;	data= new int[MaxSize];				}void push(int e);void pop(int &e);void GetTop(int &e);private:int MaxSize;int top;int *data;
};
void stack_static::push(int e)
{data[top]=e;top++;
}
void stack_static::pop(int &e)
{top--;e=data[top];
}
void stack_static::GetTop(int &e)
{if(top!=MaxSize)e=data[top-1];elsee=-1;
}
void InitStack(SqStack_dynamic &stack)
{stack.base= new int[Maxsize];stack.top=stack.base;
}
void push(SqStack_dynamic &stack,int e)
{if((stack.top-stack.base)>=Maxsize)return;*stack.top=e;stack.top++;
}
void pop(SqStack_dynamic &stack,int &e)
{if(stack.base==stack.top)return;stack.top--;e=*stack.top;	
}
int GetTop(SqStack_dynamic &stack)
{if(stack.base!=stack.top)return *(stack.top-1);elsereturn -1;
}
int main()
{SqStack_dynamic stack;InitStack(stack);push(stack,2);push(stack,5);push(stack,10);std::cout<<"------dynamic stack-----"<

#include
using namespace std;
class BinaryTreeNode{
public://initBinaryTreeNode(){data=NULL;lchild=NULL;rchild=NULL;	}BinaryTreeNode(int n){data=new int;*data=n;lchild=NULL;rchild=NULL;}
private:int *data;//dataBinaryTreeNode* lchild;//left child tree BinaryTreeNode* rchild;//right child tree
};
int main()
{BinaryTreeNode bt(5);	return 0;	
} 

//递归
void preorderTraversal(BinaryTreeNode *node)
{if(!node)return;std::cout<data<<" ";preorderTraversal(node->lchild);preorderTraversal(node->rchild); 
}
//迭代
void preoder(BinaryTreeNode *root)
{BinaryTreeNode *cur=root;std::stacks;while(cur||!s.empty()){//遍历直到最左叶子节点 while(cur){std::cout<data<<" "; s.push(cur);cur=cur->lchild;}//while结束时，cur=NULL//cur为左子节点 cur=s.top();s.pop();cur=cur->rchild;}}

	void midorderTraversal(BinaryTreeNode *node){if(!node)return;preorderTraversal(node->lchild);std::cout<data<<" ";preorderTraversal(node->rchild); }void midoder(BinaryTreeNode *root){BinaryTreeNode *cur=root;std::stacks;while(cur||!s.empty()){//遍历直到最左叶子节点 while(cur){s.push(cur);cur=cur->lchild;}//while结束时，cur=NULL//cur为左子节点 cur=s.top();std::cout<data<<" "; s.pop();cur=cur->rchild;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！