数据结构深入剖析（2）

一、静态链表
1.单链表的相对劣势
---单链表的实现严重依赖指针。
---数据元素中必须包含一个额外的指针域。
---没有指针的程序设计语言无法实现。
2.顺序表的改进
--静态链表的定义
---顺序表数组中的元素由两个数据域组成：data和next
---data用于存储数据。
---next用于存储下一个元素在数组中的下标。
3.静态链表相关定义
typedef struct _tag_StaticListNode
{
    unsigned int data;
    int next;
}TStaticListNode;
typedef struct _tag_StaticList
{
    int capacity;
    TStaticListNode header;
    TStaticListNode node[];
}TStaticList;
4.静态链表相关操作
1）获取位置为pos的元素
---判断线性表是否合法
---判断位置是否合法
---由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标。
sList->node[0] = sList->header;
for(i = 0 ; i < pos; i++){
    current = sList->node[current].next;
}
object = sList->node[current].next;
2)插入元素到位置pos的算法
---判断线性表是否合法
---判断插入位置是否合法
---在数组中查找空闲位置index
---由表头开始通过next域移动pos次后，当前元素的next域即要插入的位置
---将新元素插入并将数组长度加1.
for(i = 0; (i < pos) && (sList->node[current].next != 0); i++){
    current = sList->node[current].next;
}

sList->node[index].next = sList->node[current].next;
sList->node[current].next = index;
3)删除第pos个元素的算法
---判断线性表是否合法
---判断删除位置是否合法
---获取第pos个元素
---将第pos个元素从链表中删除
---线性表长度减1
object = sList->node[current].next;
sList->node[current].next = sList->node[object].next;
4.静态链表总结
---静态链表其实是单链表的另一种实现方式
---静态链表的实现“媒介”不是指针而是数组
---静态链表主要用于不支持指针的程序设计语言中
---静态链表的实现是一种内存管理的简易方式。

二、循环链表
1.单链表的局限
---单链表可以用于表示任意的线性关系
---有些线性关系是循环的，即没有队尾元素
2.循环链表的定义
---将链表中最后一个元素的next指针指向第一个元素。
3.游标的定义
---在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。
4.循环链表的新操作
---获取当前游标指向的数据元素。
---将游标重置指向链表中的第一个数据元素。
---将游标移动指向到链表中的下一个数据元素。
---直接指定删除链表中的某个数据元素。

Example：循环链表及约瑟夫问题求解
//.h头文件
#ifndef _CIRCLELIST_H
#define _CIRCLELIST_H


typedef void CircleList;
typedef struct _tag_CircleListNode CircleListNode;
struct _tag_CircleListNode
{
CircleListNode* next;
};
CircleList* CircleList_Create();
void CircleList_Destroy(CircleList* list);
void CircleList_Clear(CircleList* list);
int CircleList_Length(CircleList* list);
int CircleList_Insert(CircleList* list,CircleListNode* node,int pos);
CircleListNode* CircleList_Get(CircleList* list,int pos);
CircleListNode* CircleList_Delete(CircleList* list,int pos);
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
CircleListNode* CircleList_Reset(CircleList* list);
CircleListNode* CircleList_Current(CircleList* list);
CircleListNode* CircleList_Next(CircleList* list);
#endif

//.c实现
#include
#include
#include "CircleList.h"
typedef struct _tag_CircleList
{
CircleListNode header;
CircleListNode* slider;
int length;
}TCircleList;

CircleList* CircleList_Create()
{
TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));

if(ret != NULL){
ret->length = 0;
ret->header.next = NULL;
ret->slider = NULL;
}
return ret;
}

void CircleList_Destroy(CircleList* list)
{
free(list);
}

void CircleList_Clear(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
if(sList != NULL){
sList->length = 0;
sList->header.next = NULL;
sList->slider = NULL;
}
}

int CircleList_Length(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
int ret = 1;
if(sList != NULL){
ret = sList->length;
}
return ret;
}

int CircleList_Insert(CircleList* list,CircleListNode* node,int pos)
{
TCircleList* sList = (TCircleList*)list;
int i = 0;
int ret = (sList != NULL) && (pos >= 0) &&(node != NULL);
if(ret){
CircleListNode* current = (CircleListNode*)sList;
for(i = 0; (i < pos) && (current->next != NULL); i++){
current = current->next;
}
node->next = current->next;
current->next = node;

if(sList->length == 0){
sList->slider = node;
node->next = node;
}
sList->length++;
}
return ret;
}

CircleListNode* CircleList_Get(CircleList* list,int pos)
{
TCircleList* sList = (TCircleList*)list;
int i = 0;
CircleListNode* ret = NULL;

if(sList != NULL && (0 <= pos)){
CircleListNode* current = (CircleListNode*)sList;
for(i = 0; i < pos; i++){
current = current->next;
}
ret = current->next;
}
return ret;
}

CircleListNode* CircleList_Delete(CircleList* list,int pos)
{
TCircleList* sList = (TCircleList*)list;
int i = 0;
CircleListNode* ret = NULL;

if(sList != NULL && (0 <= pos)){
CircleListNode* current = (CircleListNode*)sList;
CircleListNode* first = sList->header.next;
CircleListNode* last = (CircleListNode*)CircleList_Get(sList,sList->length - 1);
for(i = 0; i < pos; i++){
current = current->next;
}
ret = current->next;
current->next = ret->next;

if(first == ret){
sList->header.next = ret->next;
last->next = ret->next;
}
if(sList->slider == ret){
sList->slider = ret->next;
}
if(sList->length == 0){
sList->header.next = NULL;
sList->slider = NULL;
}
sList->length--;
}
return ret;
}

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
TCircleList* sList = (TCircleList*)list;
int i = 0;
CircleListNode* ret = NULL;

if(sList != NULL){
CircleListNode* current = (CircleListNode*)sList;
for(i = 0; i < sList->length; i++){
if(current->next == node){
ret = current->next;
break;
}
current = current->next;
}
if(ret != NULL){
CircleList_Delete(sList,i);
}
}
return ret;
}
CircleListNode* CircleList_Reset(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
CircleListNode* ret = NULL;

if(sList != NULL){
sList->slider = sList->header.next;
ret = sList->slider;
}

return ret;
}
CircleListNode* CircleList_Current(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
CircleListNode* ret = NULL;
if(sList != NULL){
ret = sList->slider;
}
return ret;
}
CircleListNode* CircleList_Next(CircleList* list)
{
TCircleList* sList = (TCircleList*)list;
CircleListNode* ret = NULL;
if((sList != NULL) && (sList->slider != NULL)){

ret = sList->slider;
sList->slider = ret->next;
}

return ret;
}

//main文件
#include
#include
#include "CircleList.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct value
{
CircleListNode header;
int v;
};


int main(int argc, char *argv[]) 
{
int i = 0;
CircleList* list = CircleList_Create();

struct value v1;
struct value v2;
struct value v3;
struct value v4;
struct value v5;
struct value v6;
struct value v7;
struct value v8;
v1.v = 1;
v2.v = 2;
v3.v = 3;
v4.v = 4;
v5.v = 5;
v6.v = 6;
v7.v = 7;
v8.v = 8;

CircleList_Insert(list,(CircleListNode*)&v1,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v2,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v3,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v4,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v5,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v6,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v7,CircleList_Length(list));
CircleList_Insert(list,(CircleListNode*)&v8,CircleList_Length(list));

for(i = 0; i < CircleList_Length(list);i++){
struct value* pv = (struct value*)CircleList_Get(list,i);
printf("%d\n",pv->v);
}
printf("--------------约瑟夫问题求解--------------------\n");

CircleList_Reset(list);
while(CircleList_Length(list) > 0){
struct value* pv = NULL;

for (i = 1; i < 3;i++){
CircleList_Next(list);
}
pv = (struct value*)CircleList_Current(list);
printf("%d\n",pv->v);
   CircleList_DeleteNode(list,(CircleListNode*)pv);
}


CircleList_Destroy(list);
return 0;
}