首页 > 代码库 > 关于链表
关于链表
/*堆排序(大顶堆) 2011.9.14*/
#include <iostream>
#include<algorithm>
using namespace std;
void HeapAdjust(int *a,int i,int size) //调整堆
{
int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号
int max=i; //临时变量
if(i<=size/2) //如果i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆
}
}
}
void BuildHeap(int *a,int size) //建立堆
{
int i;
for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,size);
}
}
void HeapSort(int *a,int size) //堆排序
{
int i;
BuildHeap(a,size);
for(i=size;i>=1;i--)
{
//cout<<a[1]<<" ";
swap(a[1],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}
int main(int argc, char *argv[])
{
//int a[]={0,16,20,3,11,17,8};
int a[100];
int size;
while(scanf("%d",&size)==1&&size>0)
{
int i;
for(i=1;i<=size;i++)
cin>>a[i];
HeapSort(a,size);
for(i=1;i<=size;i++)
cout<<a[i]<<"";
cout<<endl;
}
return 0;
}
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
void bubbleSort(int *a,int len)
{
int i,j,change;
for(i=0;i<len;i++)
{
change=0;
for(j=len-1;j>i;j--)
{
if(a[j]<a[j-1])
{
change=1;
swap(&a[j],&a[j-1]);
}
}
if(!change)
break;
}
}
归并排序
void merge(int *a,int start,int mid,int end)
{
if(start>mid || mid >end ) return;
int i=start,j=mid+1,k=0;
int *L=(int *)malloc((end-start+1)*sizeof(int));
while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
L[k++]=a[i++];
}else {
L[k++]=a[j++];
}
}
while(i<=mid)
L[k++]=a[i++];
while(j<=end)
L[k++]=a[j++];
for(i=start,j=0;i<=end;i++,j++)
{
a[i]=L[j];
}
free(L);
}
void mergeSort(int *a, int start,int end)
{
if(start<end)
{
int mid=(start+end)/2;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end);
}
}
/*************************************************************************
这是一个二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、查找、
查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度
均为o(h),其中h是树的高度
注释很详细，具体内容就看代码吧
*************************************************************************/
#include<stdio.h>
#include<stdlib.h>
//二叉查找树结点描述
typedef int KeyType;
typedef struct Node
{
KeyType key; //关键字
struct Node * left; //左孩子指针
struct Node * right; //右孩子指针
struct Node * parent; //指向父节点指针
}Node,*PNode;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
void inseart(PNode * root,KeyType key)
{
//初始化插入结点
PNode p=(PNode)malloc(sizeof(Node));
p->key=key;
p->left=p->right=p->parent=NULL;
//空树时，直接作为根结点
if((*root)==NULL){
*root=p;
return;
}
//插入到当前结点（*root）的左孩子
if((*root)->left == NULL && (*root)->key > key){
p->parent=(*root);
(*root)->left=p;
return;
}
//插入到当前结点（*root）的右孩子
if((*root)->right == NULL && (*root)->key < key){
p->parent=(*root);
(*root)->right=p;
return;
}
if((*root)->key > key)
inseart(&(*root)->left,key);
else if((*root)->key < key)
inseart(&(*root)->right,key);
else
return;
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
PNode search(PNode root,KeyType key)
{
if(root == NULL)
return NULL;
if(key > root->key) //查找右子树
return search(root->right,key);
else if(key < root->key) //查找左子树
return search(root->left,key);
else
return root;
}
//查找最小关键字,空树时返回NULL
PNode searchMin(PNode root)
{
if(root == NULL)
return NULL;
if(root->left == NULL)
return root;
else //一直往左孩子找，直到没有左孩子的结点
return searchMin(root->left);
}
//查找最大关键字,空树时返回NULL
PNode searchMax(PNode root)
{
if(root == NULL)
return NULL;
if(root->right == NULL)
return root;
else //一直往右孩子找，直到没有右孩子的结点
return searchMax(root->right);
}
//查找某个结点的前驱
PNode searchPredecessor(PNode p)
{
//空树
if(p==NULL)
return p;
//有左子树、左子树中最大的那个
if(p->left)
return searchMax(p->left);
//无左子树,查找某个结点的右子树遍历完了
else{
if(p->parent == NULL)
return NULL;
//向上寻找前驱
while(p){
if(p->parent->right == p)
break;
p=p->parent;
}
return p->parent;
}
}
//查找某个结点的后继
PNode searchSuccessor(PNode p)
{
//空树
if(p==NULL)
return p;
//有右子树、右子树中最小的那个
if(p->right)
return searchMin(p->right);
//无右子树,查找某个结点的左子树遍历完了
else{
if(p->parent == NULL)
return NULL;
//向上寻找后继
while(p){
if(p->parent->left == p)
break;
p=p->parent;
}
return p->parent;
}
}
//根据关键字删除某个结点,删除成功返回1,否则返回0
//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
int deleteNode(PNode* root,KeyType key)
{
PNode q;
//查找到要删除的结点
PNode p=search(*root,key);
KeyType temp; //暂存后继结点的值
//没查到此关键字
if(!p)
return 0;
//1.被删结点是叶子结点，直接删除
if(p->left == NULL && p->right == NULL){
//只有一个元素，删完之后变成一颗空树
if(p->parent == NULL){
free(p);
(*root)=NULL;
}else{
//删除的结点是父节点的左孩子
if(p->parent->left == p)
p->parent->left=NULL;
else //删除的结点是父节点的右孩子
p->parent->right=NULL;
free(p);
}
}
//2.被删结点只有左子树
else if(p->left && !(p->right)){
p->left->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent == NULL)
*root=p->left;
//删除的结点是父节点的左孩子
else if(p->parent->left == p)
p->parent->left=p->left;
else //删除的结点是父节点的右孩子
p->parent->right=p->left;
free(p);
}
//3.被删结点只有右孩子
else if(p->right && !(p->left)){
p->right->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent == NULL)
*root=p->right;
//删除的结点是父节点的左孩子
else if(p->parent->left == p)
p->parent->left=p->right;
else //删除的结点是父节点的右孩子
p->parent->right=p->right;
free(p);
}
//4.被删除的结点既有左孩子，又有右孩子
//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)
//删掉后继结点,后继结点的值代替该结点
else{
//找到要删除结点的后继
q=searchSuccessor(p);
temp=q->key;
//删除后继结点
deleteNode(root,q->key);
p->key=temp;
}
return 1;
}
//创建一棵二叉查找树
void create(PNode* root,KeyType *keyArray,int length)
{
int i;
//逐个结点插入二叉树中
for(i=0;i<length;i++)
inseart(root,keyArray[i]);
}
int main(void)
{
int i;
PNode root=NULL;
KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
create(&root,nodeArray,11);
for(i=0;i<2;i++)
deleteNode(&root,nodeArray[i]);
printf("%d\n",searchPredecessor(root)->key);
printf("%d\n",searchSuccessor(root)->key);
printf("%d\n",searchMin(root)->key);
printf("%d\n",searchMax(root)->key);
printf("%d\n",search(root,13)->key);
return 0;
}
某本书上面说了，链表这个东西，实际用的并不多，但是可以提供很好的考察面试者编程技巧和思维能力的素材。这里总结一下，见过的面试题和对应的候选解法。
题一、 给定单链表，检测是否有环。
使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2。假设len1>=len2，那么指针p1由head1开始向后 移动len1-len2步。指针p2=head2，下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，否则说明两个链表没有 交点。
题三、 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。
题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。
题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。
题六、给定单链表头结点，删除链表中倒数第k个结点。
使用两个节点p1,p2，p1初始化指向头结点，p2一直指向p1后第k个节点，两个结点平行向后移动直到p2到达链表尾部(NULL),然后根据p1删除对应结点。
题八、倒转单链表
给出非递归和递归解法：
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
}*head;
// 非递归写法
Node* InverseLinkedList(Node* head)
{
if(head == NULL)
return NULL;
Node* newHead = NULL;
while(head != NULL)
{
Node* nextNode = head->next;
head->next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
// 递归写法
Node* InverseLinkedListRecur(Node* head)
{
if(head == NULL)
return NULL;
if(head->next == NULL)
return head;
Node* newHead = InverseLinkedListRecur(head->next);
Node *tmp = newHead;
while(tmp->next != NULL)
{
tmp = tmp->next;
}
tmp->next = head;
head->next = NULL;
return newHead;
}
int main()
{
// 构建链表 9->8->7->6->5->4->3->2->1->0->NULL
for(int i = 0; i < 10; i++)
{
Node* node = new Node();
node->data = i;
node->next = head;
head = node;
}
head = InverseLinkedList(head);
Node *tmp = head;
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
head = InverseLinkedListRecur(tmp);
tmp = head;
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
while(tmp != NULL)
{
Node* next = tmp->next;
delete tmp;
tmp = next;
}
}
题九、两个有序链表的合并
有两个有序链表，各自内部是有序的，但是两个链表之间是无序的
typedef struct node{
int data;
struct node * next;
}* List;
List mergeSortedLinkList(List list1, List list2)
{
List pList1,pList2,mergedList,pCurNode;
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
pList1 = list1;
pList2 = list2;
mergedList = NULL;
if (pList1==pList2)
{
mergedList = pList1;
pList1 = pList1->next;
pList2 = pList2->next;
}
else
{
if (pList1->data <= pList2->data)
{
mergedList = pList1;
pList1 = pList1->next;
}
else
{
mergedList = pList2;
pList2 = pList2->next;
}
}
pCurNode = mergedList;
while(pList1 && pList2)
{
if (pList1==pList2)
{
pCurNode->next = pList1;
pCurNode = pList1;
pList1 = pList1->next;
pList2 = pList2->next;
}
else
{
if (pList1->data <= pList2->data)
{
pCurNode->next = pList1;
pCurNode = pList1;
pList1 = pList1->next;
}
else
{
pCurNode->next = pList2;
pCurNode = pList2;
pList2 = pList2->next;
}
}
}
pCurNode->next =pList1?pList1:pList2;
return mergedList;
}
题十、找出链表的中间元素
单链表的一个比较大的特点用一句广告语来说就是“不走回头路”，不能实现随机存取（random access）。如果我们想要找一个数组a的中间元素，直接a[len/2]就可以了，但是链表不行，因为只有a[len/2 - 1] 知道a[len/2]在哪儿，其他人不知道。因此，如果按照数组的做法依样画葫芦，要找到链表的中点，我们需要做两步（1）知道链表有多长（2）从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n（n为链表的长度）的时间复杂度了。有没有更好的办法呢？有的。想法很简单：两个人赛跑，如果A的速度是B的两倍的话，当A到终点的时候，B应该刚到中点。这只需要遍历一遍链表就行了，还不用计算链表的长度。
面试的时候，书写程序要注意以下几点
1.确认了解题意，如果对题意了解不清，应该向面试人员问清楚
2.明确题意后，首先思考找到一个复杂度可以接受的正确算法，并表述出来，注意可以在草稿纸上写写划划，进行验证
3.观察复杂度能否再次降低
4.书写程序时，一定要认真，坚决防止出现逻辑错误，并根据程序具体分析可能的极端情况，处理好边界，并自己进行用例测试，以验证程序。
节点的定义如下：
typedef struct list {
int key;
struct list *next;
}list;
(1)已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)
list * reverse(list * head){
list * h = head;
list * new_head = NULL,*temp;
if(h==NULL) return h;//如果是空链表
do{
temp = h;
h = h -> next;
temp -> next = new_head;
new_head = temp;
}while(h != NULL && h != head)//检测是循环链表
return new_head;
}
其实还要注意一点，链表内部是否包含小环。
(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小
相同）
list * merge (list *list1_head, list *list2_head){
}
其实需要问一下，head1 head2是否都是从大到小，这点一定要明确，不能默认两个是相同的规格排序。
(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)
list * merge (list *list1_head, list *list2_head){
list * res;
if(list1_head == NULL) return list2_head;
if(list2_head == NULL) return list1_head;
if(list1_head->key > list2_head->key){
res = list1_head;
res->next = merge(list1_head->next,list2_head);
}else{
res = list2_head;
res->next = merge(list1_head,list2_head->next);
}
return res;
}
(4)写一个程序，计算链表的长度
unsigned int list_len(list *head){
unsigned int len = 0;
list * h = head;
if(h == NULL)return 0;
d0{
len++;
h = h->next;
}while(h != NULL && h != head)
return len;
}
如果是循环链表？
(5)有一个链表L,其每个节点有2个指针，一个指针next指向链表的下个节点，另一个random随机指向链表中的任一个节点，可能是自己或者为空，写一个程序，要求复制这个链表的结构并分析其复杂性。
这个题目的思路很巧妙。当然简单的方法，可以利用一个map或者hash，将链表的random指针的指向，保存起来。这样有O(n)存储空间的浪费，时间基本可以接近O(n).
实际上可以这样来做：我们将新的链表节点，插入到原来链表节点当中，并且修改原来的链表的random指针，使得该指针由我们现在的新节点所有。实际上形成下面这样一种结构，同时将原来o的random指针的值，复制给它后面的现在的@的random指针，该结构如下：
o->@->o->@->o->@->NULL
现在可以利用@拥有的random指针方便的找到它真正的random指针。因为原来的@的random指针指向o的random指针，只要把让@->random=@->random->next,random就是真正的那个指针了，然后我们再把@从这个链表中删除。
(6)给你一个单向链表的头指针，可能最后不是NULL终止，而是循环链表。题目问你怎么找出这个链表循环部分的第一个节点。
1。如果允许修改节点的数据结构的话，那么就在每个节点上设置一个标志位表示是否被访问过。这样遍历时遇到已访问节点即是循环的第一个节点。
2。如果不允许修改节点，那么就在外部用一个hashmap记录下所有的已访问节点。遍历时先查找这个hashmap，节点不存在则加入，已存在则该节点就是循环的第一个节点。
(7)（华为面试题）找出单向链表中中间结点
这个可以借鉴上面的方法，利用步长为1，步长为2指针，当步长为2的指针到达末尾时，指针1就刚好达到中间。
(8)题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
实际上我们可以将该节点的下一个节点的值copy到这个节点，然后删除下一个节点。这样实际上就将一个不能处理的情况，通过一种技巧转化成了我们可以处理的正常情况。
但是还需要注意下面这个边界情况：如果要删除的是尾指针？这就意味着当前节点没有下一个节点。
通过这点我们也可以发现，如果认真考虑各个因素，思路清晰，还是很容易发现各种异常情况的，保证严谨的思考。
关于链表