试写出循环链表长度的算法

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);
}