試寫出循環鏈表長度的演算法

1. 用C語言實現鏈表的演算法

這個是我們數據結構上機實驗的鏈表問題，

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(LinkNode)
typedef int Datatype;
typedef int Status;
typedef struct LinkNode{
Datatype data;
struct LinkNode *next;
} LinkNode,*LinkList;
typedef struct OrderedList
{
LinkNode *head,*tail;
int Listsize;
} OrderedList;//有序循環鏈表的頭節點head,尾接接節點 tail及長度Listsize
Status InitList(OrderedList *List)//生成循環鏈表頭節點
{
List->tail=List->head=(LinkList)malloc(LEN);
if(List->head==NULL)
return 0;
else
{
List->head->next=List->tail;
List->tail->next=List->head;
List->Listsize=0;

return 1;
}
}
void OrderedInsert(OrderedList *List,Datatype data)//每調用一次有序插入data形成有序的(從小到大)的鏈表

{ LinkNode *p ,*q;

if(List->head==List->tail->next)
{
p=(LinkNode*)malloc(LEN);
p->data = data;
List->head->next=p;
p->next=List->tail;
List->Listsize++;
}
else
{
p=List->head->next;
q = List->head;
while(p->data<data&&p!=List->tail)
{
q = p;
p=p->next;
}
if(p->data==data)
{printf("YOu have input the same datas %d\n\t YOu should input another data \n",data);
scanf("%d",&data);
OrderedInsert(List,data);
}
else
{
p=(LinkNode*)malloc(LEN);
p->data = data;
p->next = q->next;
q->next = p;
List->Listsize++;
}
}
}
void Creatset(OrderedList *List)//多次調用OrderedInsert()生成有序鏈表即集合List
{
Datatype data;
int setsize , i=0;
printf("Please input the setsize you want to creat:\n");
scanf("%d",&setsize);
InitList(List);
if(setsize==0)
printf("You needen't input any data\n");
else if(setsize==1)
printf("Please input a single data\n");
else
printf("Please input %d different datas;\n",setsize);
while(i<setsize||setsize>List->Listsize)//當循環次數i小於setsize或者集合內實際元素數List.Listsize小於setsize時一直循環下去
{
scanf("%d",&data);
OrderedInsert(List,data);
i++;
}
}

void Append(OrderedList *List,Datatype data)//在循環鏈表的最後面追加 一個data
{
LinkNode *p;
p=(LinkNode*)malloc(LEN);
p->data=data;
List->tail=List->tail->next=p;
List->tail->next=List->head;
List->Listsize+=1;
}
void MergeList(OrderedList La,OrderedList Lb,OrderedList *Lc)//有序循環鏈表ListLa,ListLb求並集生成ListLc
{
LinkList Pa,Pb;
Pa=La.head->next;Pb=Lb.head->next;
while(Pa!=La.tail&&Pb!=Lb.tail)
{
if(Pa->data<=Pb->data)
{
Append(Lc,Pa->data);
Pa=Pa->next;
}

else {
Append(Lc,Pb->data);Pb=Pb->next;
}
}
while(Pa!=La.tail)
{ Append( Lc,Pa->data);Pa=Pa->next;}

while(Pb!=Lb.tail)
{ Append(Lc,Pb->data);Pb=Pb->next;}

}
void Print(OrderedList List)
{
LinkNode *p;
p=List.head->next;
if(p->next==List.head)
printf("No Elem\n");
while(p!=List.head)
{ printf("%5d",p->data);p=p->next; }
printf("\n");
}
void main()
{
OrderedList ListLa,ListLb,ListLc;
Creatset(&ListLa);
Creatset(&ListLb);
InitList(&ListLc);
MergeList(ListLa,ListLb,&ListLc);
printf("The orgnial list ListLa,ListLb:\n");
Print(ListLa);
Print(ListLb);
printf("The Merge list ListLc;\n");
Print(ListLc);
}

2. 求幾個有關鏈表的最基本演算法

這個也太多了！
1.循環單鏈表,且含有頭結點的
p = head->next;
for(len=0；p->next!=head；p=p->next)
{
len++ //長度加1
}
2.插入
Status ListInsert(DuLinkList L, int i, ElemType e)
{
DuLinkList p, s;
//i值不合法
if(i < 1 || i > ListLength(L) + 1) return ERROR;

//在L中確定第i個元素前驅的位置指針p
p = GetElemP(L, i - 1);

//p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)
if(!p) return ERROR;

//給插入的數據分配空間
s = (DuLinkList)malloc(sizeof(DuLNode));

//如果為空，分配失敗
if(!s) return OVERFLOW;

//在第i-1個元素之後插入
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

return OK;
}
刪除
Status ListDelete(DuLinkList L,int i,ElemType *e)
{
DuLinkList p;

// i值不合法
if(i < 1) return ERROR;

// 在L中確定第i個元素的位置指針p
p = GetElemP(L, i);

// p=NULL,即第i個元素不存在
if(!p) return ERROR;
*e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
3.帶有頭結點
p=head->next;
head->next =NULL;
q= head;
while(p)
{
q->next = p;
q = p;
p=p->next
}
4.帶頭結點
p=head->next;
head->next = head;
q = head;
while(p!=head)
{
if(head->next = head){q->next=p;q->next = head;}
else{q->next = p;}
q = p;
}
5.帶頭結點
p = head->next;
p->prior = NULL;
q = head;
while(p)
{
q->prior = p;
q->next = p->next;
p->next->prior = q;
p->next = q;

}

3. 循環鏈表長度的演算法

p=head->next
int count =0;
while(p!=head){
p = p->next;
count++;
}
思路大概是這樣吧，當從頭結點開始開始指針移動，循環一次後又回到頭結點

4. 循環鏈表長度測量的演算法

定義一個指針,選取一個鏈表的切入點,並用定義的指針儲存切入節點保存的指針值.遍歷鏈表,記數並比較節點儲存的指針和定義的指針,相等時跳出.
上面應該是最基本的長度測量了.應該還有其他演算法的,下去要好好研究下.

5. 寫出求雙向循環鏈表長度的演算法。(注:頭結點不算）

int ListLength_Dul(DuLinkList L) /* 初始條件：L已存在。操作結果： */
{
int i=0;
DuLinkList p=L->next; /* p指向第一個結點 */
while(p!=L) /* p沒到表頭 */
{ i++; p=p->next; }
return i;
}

6. 試編寫一個演算法,計算帶頭結點的循環單鏈表的長度

int length(struct list * head)
{
int i = 0;
struct list *tmp;
if( head == NULL)
return 0;
if( head -> next == head)
return 1;
tmp = head->next;
while(tmp != head)
{
i++;
tmp = tmp -> next;
}
return i;
}

7. 用c語言試寫出計算循環列表長度的演算法

這個應該是沒錯的啊，難道你是覺得j初值應該等於1看
帶頭結點的單鏈表啊，指針每移動一次，長度+1，然後返回這個長度值啊。

8. 有一個循環單鏈表的長度大於1，表中既無頭結點也無頭指針。S為指向鏈表中某結點的指針，寫演算法，刪除結點S

//1、假設在長度大於1的單循環鏈表中，
//既無頭結點也無頭指針。s為指向某個結點的指針，試編寫演算法刪除結點*s的直接前驅結點。
#include <iostream>
using namespace std;

typedef struct list
{
struct list *next;
int data;
}List,*LinkList;

//創建循環鏈表
void CreatLinkList(LinkList &L,int n)
{
LinkList p,r;
L=new List;
// L->next=NULL;
cin>>L->data;
r=L;
p=L;
for(int i=0;i<n-1;i++)
{
p=new List;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
r->next=L;
}

//刪除結點
/*
思路 通過當前指針的下下個指針中的數據與要刪除結點的後繼結點的數據相比較
如果相等則說明 當前結點的下一個結點為要刪除的結點

返回值 -1 刪除頭結點 出現錯誤
返回值 1 成功刪除結點
*/
int deleteLinkList(LinkList &L,int data)//刪除值為data結點的前驅結點
{
LinkList p=L;
if(L->next->data==data)
{
cout<<"不能刪除頭結點";
return -1;
}

//判斷 如果結點的下下個結點不是要找的結點則跳到下一個結點
while(p->next->next->data!=data)
{
p=p->next;
}
//如果找到了 當前結點的下一個結點為刪除的結點
p->next=p->next->next;
return 1;
}

void displayLinkList(LinkList &L)
{
LinkList p=L->next;

cout<<L->data<<" ";
while(p!=L)
{
cout<<p->data<<" ";
p=p->next;

}

}

int main()
{
LinkList L;
int n;//鏈表長度
int flag=0;//狀態
cout<<"輸入循環鏈表長度 ";
cin>>n;
CreatLinkList(L,n);
LinkList s;//指針s
cout<<"輸入想刪除的值的下一位數 ";
cin>>s->data;
flag=deleteLinkList(L,s->data);
if(flag==1)
{
cout<<"刪除後的結果為 ";
displayLinkList(L);
}
if(flag==-1)
cout<<"操作錯誤";

}

9. 循環鏈表演算法原理和順序表演算法原理

其中線性表內含順序表和鏈表。順序表較為簡單，僅僅需要一個數組就可以完成，當然最好也要添加一個表示長度的數據成員，如size。而鏈表，顯然比較多變看，小可不才，用了將近三天的時間才能明白，不能不說見笑於大方之家；皆因鏈表之中還有循環鏈表，雙向鏈表，雙向循環鏈表。好了，言歸正傳：循環鏈表的程序奉上：
鏈表，不過增（insert）刪（delete）改（update）查（select）而已。在於Java程序中，還要加上構造（Java有垃圾回收機制，故沒有析構，但可以手動回收）。先看代碼如下：
1、關於構造函數，小生理解到：需要什麼樣的初始化，就寫出什麼樣的構造函數，當然，沒有時類也會人性化的構造一個空的構造函數；本人就節點有一個構造函數
2、在方法中，注意index的具體代表就行。其中，在找上一節點時，很多重復了，可以另外寫入一個函數中。
3、最後只是一個測試形式的，可以自己設置
4、自認為一個比較簡單的程序了
packagelink;

classNode {
publicintnum;
publicNodenext;

publicNode(intnum, Node next) {
this.num= num;
this.next= next;
}
}

publicclassCycleList {
publicNodehead;
publicintsize;

publicvoidinsertHead(intelement){//在頭結點的地方插入 if(size== 0){
head=newNode(element,head);
}else{
Node no =head;
head=newNode(element, no);
}
size++;
}

publicvoidinsert(intindex,intelement) {//插入元素
if(size== 0) {
head=newNode(element,head);
}else{
if(index < 0) {
index = 0;
}
if(index >size) {
index =size;
}
Node no1 =head;
for(inti = 0; i < index - 1; i++) {
no1 = no1.next;
}
Node no2 =newNode(element, no1.next);
no1.next= no2;
}
size++;
}

publicvoiddelete(intindex) { //刪除函數
if(index < 0) {
index = 0;
}
if(index >size) {
index =size;
}
Node no3 =head;
for(inti = 0; i < index - 1; i++) {
no3 = no3.next;
}
no3.next= no3.next.next;

size--;
}

publicvoidselect() { //查詢所有元素
intsizelong =size;
Node no4 =head;
for(inti = 0; i < sizelong; i++) {
System.out.print(no4.num);
no4 = no4.next;
}
}

publicvoipdate(intindex,intelement){//更換index位置的內容
Node no7 =head;
for(inti=0; i<index-1; i++){
no7 = no7.next;
}
no7.num= element;
}

publicvoidsel(intindex){ //查詢index位置的內容
Node no8 =head;
for(inti=0; i<index-1; i++){
no8 = no8.next;
}
System.out.println(no8.num);
}

publicstaticvoidmain(String[] args) {
CycleList cl =newCycleList();
cl.insert(0, 4); // index代表第幾個後面，當然，第0個後面，即為插頭節點
cl.insert(2, 2); //無論插入還是刪除
cl.insert(3, 5); //更改很准確
cl.insert(4, 6); //查詢單個也是可以的
cl.insert(5, 9);

cl.select();
System.out.print(" ----");
cl.insert(0, 8);
cl.select();
System.out.print(" ----");
cl.insertHead(3);
cl.select();
System.out.println("------");
cl.delete(3);
cl.select();
System.out.println("---------");
cl.update(1, 1);
cl.select();
System.out.print("----");
cl.sel(0);
}
}
實現順序表各種基本運算的演算法
2007-04-29 12:44:04| 分類：數據結構程序| 標簽：|字型大小大中小 訂閱

//實現順序表各種基本運算的演算法.h#include<stdio.h>
#include<malloc.h>
#define MaxSize 50
typedef char ElemType;typedef struct
{ElemType elem[MaxSize]; //順序表類型定義
int length;
}SqList;void InitList(SqList *&L) //初始化順序表L
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}void DestroyList(SqList *L) //釋放順序表L.
{
free(L);
}int ListEmpty(SqList *L) //判斷順序表L是否為空表.
{
return(L->length==0);
}
int ListLength(SqList *L)
{
return(L->length);
} void DispList(SqList *L)
{
int i;
if(ListEmpty(L))return;
for(i=0;i<L->length;i++)
printf("%c ",L->elem[i]);
printf("\n");
}int GetElem(SqList *L,int i,ElemType &e)
{
if(i<1 || i>L->length)
return 0;
e=L->elem[i-1];
return 1;}int LocateElem(SqList *L,ElemType e)
{int i=0;
while(i<L->length && L->elem[i]!=e)i++;
if(i>=L->length)
return 0;
else
return i+1;
}int ListInsert(SqList *&L,int i,ElemType e)
{//在順序表L中第i個位置上插入元素e.
int j;
if(i<1 || i>L->length+1)
return 0;
i--;
for(j=L->length;j>i;j--)
L->elem[j]=L->elem[j-1];
L->elem[i]=e;
L->length++;
return 1;
}int ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if(i<1 || i>L->length)
return 0;
i--;
e=L->elem[i];
for(j=i;j<L->length-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
return 1;
}
//實現順序表各種基本運算的演算法.cpp#include"實現順序表各種基本運算的演算法.h"
#include<stdio.h>void main()
{
SqList *L;
ElemType e;
printf("(1)初始化順序表L:\n");
InitList(L);
printf("(2)依次採用尾插法插入a,b,c,d,e元素\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("(3)輸出順序表L:");
DispList(L);
printf("(4)順序表L長度=%d\n",ListLength(L));
printf("(5)順序表L為%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("(6)順序表L的第3個元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));
printf("(8)在第4個元素位置上插入f元素\n");
ListInsert(L,4,'f');
printf("(9)輸出順序表L:");
DispList(L);
printf("(10)刪除L的第3個元素\n");
ListDelete(L,3,e);
printf("(11)輸出順序表L:");
DispList(L);
printf("(12)釋放順序表L\n");
DestroyList(L);
}