1. 循環單鏈表解決約瑟夫問題演算法
用一組地址任意的存儲單元存放線性表中的數據元素。 以元素(數據元素的映象) + 指針(指示後繼元素存儲位置) = 結點 (表示數據元素 或 數據元素的映象) 以「結點的序列」表示線性表 稱作線性鏈表(單鏈表) 單鏈表是一種順序存取的結構,為找第 i 個數據元素,必須先找到第 i-1 個數據元素。 因此,查找第 i 個數據元素的基本操作為:移動指針,比較 j 和 i 單鏈表 1、鏈接存儲方法 鏈接方式存儲的線性表簡稱為鏈表(Linked List)。 鏈表的具體存儲表示為: ① 用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的,也可以是不連續的) ② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系,在存儲每個結點值的同時,還必須存儲指示其後繼結點的地址(或位置)信息(稱為指針(pointer)或鏈(link)) 注意: 鏈式存儲是最常用的存儲方式之一,它不僅可用來表示線性表,而且可用來表示各種非線性的數據結構。 2、鏈表的結點結構 ┌──┬──┐ │data│next│ └──┴──┘ data域--存放結點值的數據域 next域--存放結點的直接後繼的地址(位置)的指針域(鏈域) 注意: ①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。 ②每個結點只有一個鏈域的鏈表稱為單鏈表(Single Linked List)。 【例】線性表(bat,cat,eat,fat,hat,jat,lat,mat)的單鏈表示如示意圖 3、頭指針head和終端結點指針域的表示 單鏈表中每個結點的存儲地址是存放在其前趨結點next域中,而開始結點無前趨,故應設頭指針head指向開始結點。 注意: 鏈表由頭指針唯一確定,單鏈表可以用頭指針的名字來命名。 【例】頭指針名是head的鏈表可稱為表head。 終端結點無後繼,故終端結點的指針域為空,即NULL。 4、單鏈表的一般圖示法 由於我們常常只注重結點間的邏輯順序,不關心每個結點的實際位置,可以用箭頭來表示鏈域中的指針,線性表(bat,cat,fat,hat,jat,lat,mat)的單鏈表就可以表示為下圖形式。 5、單鏈表類型描述 typedef char DataType; //假設結點的數據域類型為字元 typedef struct node{ //結點類型定義 DataType data; //結點的數據域 struct node *next;//結點的指針域 }ListNode typedef ListNode *LinkList; ListNode *p; LinkList head; 注意: ①*LinkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念上更明確) ②*LinkList類型的指針變數head表示它是單鏈表的頭指針 ③ListNode類型的指針變數p表示它是指向某一結點的指針 6、指針變數和結點變數 ┌────┬────────────┬─────────────┐ ││ 指針變數 │ 結點變數 │ ├────┼────────────┼─────────────┤ │ 定義 │在變數說明部分顯式定義 │在程序執行時,通過標准 │ ││ │函數malloc生成 │ ├────┼────────────┼─────────────┤ │ 取值 │ 非空時,存放某類型結點 │實際存放結點各域內容 │ │ │的地址 ││ ├────┼────────────┼─────────────┤ │操作方式│ 通過指針變數名訪問 │ 通過指針生成、訪問和釋放 │ └────┴────────────┴─────────────┘ ①生成結點變數的標准函數 p=( ListNode *)malloc(sizeof(ListNode)); //函數malloc分配一個類型為ListNode的結點變數的空間,並將其首地址放入指針變數p中 ②釋放結點變數空間的標准函數 free(p);//釋放p所指的結點變數空間 ③結點分量的訪問 利用結點變數的名字*p訪問結點分量 方法一:(*p).data和(*p).next 方法二:p-﹥data和p-﹥next ④指針變數p和結點變數*p的關系 指針變數p的值——結點地址 結點變數*p的值——結點內容 (*p).data的值——p指針所指結點的data域的值 (*p).next的值——*p後繼結點的地址 *((*p).next)——*p後繼結點 注意: ① 若指針變數p的值為空(NULL),則它不指向任何結點。此時,若通過*p來訪問結點就意味著訪問一個不存在的變數,從而引起程序的錯誤。 ② 有關指針類型的意義和說明方式的詳細解釋 可見,在鏈表中插入結點只需要修改指針。但同時,若要在第 i 個結點之前插入元素,修改的是第 i-1 個結點的指針。 因此,在單鏈表中第 i 個結點之前進行插入的基本操作為: 找到線性表中第i-1個結點,然後修改其指向後繼的指針。
2. 順序表,單鏈表,雙鏈表,單循環鏈表,循環雙鏈表各自有什麼特點和區別緊急....求大神,最好詳細一點
訪問方式: 單鏈表:如果訪問任意結點每次只能從頭開始順序向後訪問 單循環鏈表:可以從任何一個結點開始,順序向後訪問到達任意結點 雙向鏈表:可以從任何結點開始任意向前向後雙向訪問操作:單鏈表和單循環鏈表:只能在當前結點後插入和刪除雙鏈表:可以在當前結點前面或者後面插入,可以刪除前趨和後繼(包括結點自己)存儲:單鏈表和單循環鏈表存儲密度大於雙鏈表
3. 數據結構單循環鏈表
題中沒有一個答案是正確的。應該是:
s=rear->link;
rear->link=s->link;
delete s;
4. 單向循環鏈表
演算法f 30的功能是,刪除並返回鏈表中指針s所指結點的前驅
你的程序並不是實現上面的功能,
而是實現刪除並返回鏈表中指針s所指結點
typedef struct node //鏈表結點結構體
{
DataType data; //鏈表結點成員:數值
struct node *next; //鏈表結點成員:後續結點指針
}*LinkList;
DataType f 30(LinkList s) //將循環鏈表的s結點指針作為參數傳遞進來
{
LinkList pre,p; //聲明兩個結構體變數
DataType e;
pre=s; //pre指向s結點
p=s->next; //p指向s結點的下一結點(也就是p指向pre的後繼)
while( p!=s) //當p不指向s指向的結點,這個是用於判斷循環鏈表從s結點開始遍歷,遍歷是否完畢的
{
pre=p; //pre指向它的後續結點,也就是現在的p
p=p->next; //p指向p的後續,這樣始終保證,pre指向p的前驅
}
//當上述循環執行完畢後,p指向s,pre指向s的前驅
pre ->next=p->next; //此時pre指向s的前驅,p指向s,所以這一句就將s的前驅的next指向了s的next,將s結點從鏈表中取出
e=p->data;
free(p); //刪除p指向的結點,也就是s結點
return e;
}
5. 線性表在最後一元素後插一元素和刪第一元素,僅有頭指針和僅有尾指針的單循環鏈表哪個存儲方式運算時間少
既然是單鏈表, 刪除 只有尾指針就夠了。。
插入就要遍歷到前一個指針, 然後就插入唄。。。
都是O1
6. 編寫程序,建立一個帶有節點的單向鏈表,輸入字元串,並按從小到大順序組織到鏈表中
int main()
{
Link head; //鏈表(不帶頭節點)
int n;
printf("輸入鏈表的長度n: ");
scanf("%d",&n);
printf("連續輸入%d個數據(以空格隔開): ",n);
head=CreateLink(n);
printf(" 原本鏈表的節點是: ");
DispLink(head);
LinkSort(head);
printf(" 從大到小排序之後: ");
DispLink(head);
printf("
");
return 0;
}
鏈表的具體存儲表示為:
① 用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的,也可以是不連續的)
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系,在存儲每個結點值的同時,還必須存儲指示其後繼結點的地址(或位置)信息(稱為指針(pointer)或鏈(link))
鏈式存儲是最常用的存儲方式之一,它不僅可用來表示線性表,而且可用來表示各種非線性的數據結構。
以上內容參考:網路-單鏈表
7. 用帶頭指針的單循環鏈表實現隊列和用帶尾指針的單循環鏈表實現隊列,哪種方法更好
尾指針。
頭指針的話,雖然出隊列只要一步操作,但入隊列操作需要先遍歷到尾部,再插入新結點,復雜度是O(n)。
尾指針的話,入隊列只要直接在尾部插入新結點即可,出隊列也只要把尾結點的next指向下一個結點即可。兩種操作都是O(1)復雜度。
8. C++ 單向循環鏈表
我實在不知道你們這個題目是什麼意思,竟然繼承鏈表來實現隊列,幫你實現了,VC6.0通過
//list.h
#ifndef LIST_H
#define LIST_H
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
class List
{
public:
List();
~List();
List(List&rhs);
List &operator=(List&);
int operator >>(int x);//讓>>從尾部輸入x
int operator <<(int x);//讓<<刪除x
virtual void push(int x);
void push(int x,int idx);
void deletex (int x);
virtual void pop();
virtual int top();
bool empty();
int get_num()
{
return m_nNum;
}
Node *get_head()
{
return m_pHead;
}
protected:
int m_nNum;
Node *m_pHead;
};
List::List()
{
m_nNum=0;
m_pHead=new Node;
m_pHead->data=NULL;
m_pHead->next=NULL;
}
List::List(List&rhs)
{
if(this->get_num!=rhs.get_num)
{
cout<<"鏈變大小不同,不能復制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
}
List&List::operator=(List&rhs)
{
if(this->get_num()!=rhs.get_num())
{
cout<<"鏈變大小不同,不能復制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
return *this;
}
List::~List()//釋放所有的內存
{
Node *i=m_pHead->next;
while(i!=m_pHead)
{
Node *j=i->next;
delete i;
i=j;
}
delete m_pHead;
}
void List::pop()
{
if(empty())
{
cout<<"鏈表為空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
--m_nNum;
return;
}
}
void List::push(const int x,const int idx)//在idx位置後插入x
{
if(m_nNum==0)
{
Node *idx_node=new Node;
m_pHead->next=idx_node;
idx_node->data=x;
idx_node->next=m_pHead;
}
else
{
Node *tmp=m_pHead;
for(int i=0;i<idx;++i)
{
tmp=tmp->next;
}
Node *tmpnext=tmp->next;
Node *idx_node=new Node;
tmp->next=idx_node;
idx_node->data=x;
idx_node->next=tmpnext;
}
++m_nNum;
}
void List::push(const int x)
{
push(x,m_nNum);
}
void List::deletex (int x)//刪除值為x的所有點
{
Node *tmp=m_pHead;
int idx=0;
while(idx<m_nNum)
{
Node *preNode=tmp;
tmp=tmp->next;
if(tmp->data==x)
{
Node*tmpNext=tmp->next;
tmp->next=tmpNext;
delete tmp;
tmp=tmpNext;
++idx;
}
tmp=tmp->next;
++idx;
}
}
inline int List::top ()
{
if(empty())
{
cout<<"空鏈表"<<endl;
return false;
}
return m_pHead->next->data ;
}
inline bool List::empty()
{
return m_nNum==0;
}
int List::operator <<(int x)
{
deletex(x);
return 0;
}
int List::operator >>(int x)
{
push(x);
return 0;
}
#endif
////deque.h
#ifndef QUEUE_H
#define QUEUE_H
#include "list.h"
class Queue:public List
{
public:
Queue(){}
Queue(Queue&);
virtual void pop();
virtual void push(int x);
virtual int top();
};
Queue::Queue(Queue&rhs)
{
if(this->get_num!=rhs.get_num)
{
cout<<"隊列大小不同,不能復制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
}
void Queue::pop()
{
if(empty())
{
cout<<"隊列為空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
return;
--m_nNum;
}
}
int Queue::top()
{
if(empty())
{
cout<<"隊列為空"<<endl;
return false;
}
return m_pHead->next->data ;
}
void Queue::push(int x)
{
Node *new_node=new Node;
Node *tmp=m_pHead;
for(int i=0;i<m_nNum;++i)
{
tmp=tmp->next;
}
tmp->next=new_node;
new_node->next =m_pHead;
new_node->data =x;
++m_nNum;
}
#endif
///main.cpp
/*--------------------------
這個主函數用於測試list
#include"list.h"
#include<iostream>
using namespace std;
int main()
{
List xx;
if(xx.empty())
cout<<"空"<<endl;
for(int i=0;i<3;++i)
xx.push(i);
cout<<xx.top()<<endl;
xx.pop();
cout<<xx.top()<<endl;
return 0;
}
-----------------------------------*/
#include "queue.h"
#include<iostream>
using namespace std;
int main()
{
List *xx=new Queue;//檢驗多態
xx->pop();
for(int i=0;i<3;++i)
xx->push(i);
cout<<xx->top()<<endl;
xx->pop();
cout<<xx->top()<<endl;
return 0;
}