#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
#define DEFAULT_SIZE 5
typedef struct StaticLinkedNode
{
char data;
int next;
}*NodePtr;
typedef struct StaticLinkedList
{
NodePtr nodes;
int* used;
}*ListPtr;
ListPtr initLinkedList()
{
ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticLinkedNode));
tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE);//nodes就是一个数组
tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE);//used是一个表示是否被占用的数组
tempPtr->nodes[0].data = '\0';
tempPtr->nodes[0].next = -1;//NULL
// Only the first node is used.
tempPtr->used[0] = 1;
for(int i = 1;i<DEFAULT_SIZE;i++)
{
tempPtr->used[i] = 0;
}
return tempPtr;
}
/*打印静态链表*/
void printList(ListPtr paraListPtr)
{
int p = 0;
while(p!=-1)
{
cout<<paraListPtr->nodes[p].data<<" ";
p = paraListPtr->nodes[p].next;
}
cout<<endl<<endl;
}
/*任意位置插入结点*/
void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition)
{
int p,q,i;
// Step 1. Search to the position.
p = 0;
for(i = 0;i < paraPosition;i++)
{
p = paraListPtr->nodes[p].next;
if(p == -1)
{
printf("The position %d is beyond the scope of the list.\r\n", paraPosition);
return;
}
}
// Step 2. Construct a new node.
for(i = 1;i<DEFAULT_SIZE; i ++)
{
if(paraListPtr->used[i] == 0)//找到没有运用的空间
{
cout<<"Space at "<<i<<" allocated"<<endl<<endl;
paraListPtr->used[i] = 1;
q = i;
break;
}
}
if(i == DEFAULT_SIZE)
{
cout<<"No Space"<<endl<<endl;
return;
}
paraListPtr->nodes[q].data = paraChar;
cout<<"Linking.....\n"<<endl;
paraListPtr->nodes[q].next = paraListPtr->nodes[p].next;
paraListPtr->nodes[p].next = q;
}
/*删除结点*/
void deleteElement(ListPtr paraListPtr, char paraChar)
{
int p,q;
p=0;
while((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data != paraChar))//本结点next指针域所指向的下一
//个结点的数据域
{
p = paraListPtr->nodes[p].next;
}//循环结束，p是目标结点的上一个结点的指针域指向数据域为paraChar的结点
if(paraListPtr->nodes[p].next == -1)//p走到最后一位的下一个，即先想去看空结点的时候，还没有找到数据域为paraChar的结点。表明没有该结点
{
cout<<paraChar<<"Cannot Find!"<<endl;
return;
}
q = paraListPtr->nodes[p].next;//记录目标结点的下标，q指向目标结点
paraListPtr->nodes[p].next = paraListPtr->nodes[q].next;//使目标结点的上一个结点指向目标结点的下一个结点
// This statement is identical to free(q)
paraListPtr->used[q] = 0;
}
void Test()
{
ListPtr tempList = initLinkedList();
insertElement(tempList, 'H', 0);
insertElement(tempList, 'e', 1);
insertElement(tempList, 'l', 2);
insertElement(tempList, 'l', 3);
insertElement(tempList, 'o', 4);
printList(tempList);
printf("Deleting 'e'.\r\n");
deleteElement(tempList, 'e');
printf("Deleting 'a'.\r\n");
deleteElement(tempList, 'a');
printf("Deleting 'o'.\r\n");
deleteElement(tempList, 'o');
printList(tempList);
insertElement(tempList, 'x', 1);
printList(tempList);
}
int main()
{
Test();
system("pause");
return 0;
}
typedef struct _StatickLinkNode
{
int data;
int next;
}StackLinkNode;
typedef struct _StatickLink
{
StackLinkNode *Data;
int *used;
}StaticLink,*StatickLinkPtr;
bool initStaticLink(StatickLinkPtr &L)
{
L = new StaticLink;
L->Data = new StackLinkNode[MaxSize];
L->used = new int[MaxSize];
if(!L||!L->Data||!L->used)
return false;
L->Data[0].data = 0;
L->Data[0].next = null;
L->used[0] = 1;
for(int i=1;i<MaxSize;i++)
{
L->used[i] = 0;
}
return true;
}
void InsertByTail(StatickLinkPtr &L,int e)
{
int pos = 0,i,q = 1,r=0;
//查找最后一个结点
while(pos != -1)
{
r = pos;//r记录尾结点的下标
pos = L->Data[r].next;
}//pos = 3
for(i = 1;i<MaxSize;i++)
{
if(L->used[i] == 0)
{
cout<<endl<<"找到空闲空间:"<<i<<endl;
L->used[i] = 1;
q = i;
break;
}
}
if(pos>=MaxSize || i>=MaxSize)
{
cout<<"无法在尾部插入！！"<<endl;
return;
}
L->Data[q].data = e;//新的尾结点的数据域存放新的数据
L->Data[q].next = null;//指针域为-1，成为新的尾结点
L->Data[r].next = q; // 原来的尾结点的指针域，指向新的尾结点
}
void insertElementByData(StatickLinkPtr &L,int e,int element)// 新元素值 目标结点的元素值
{
int pos = 0,i,q,last=0;
for(i = 1;i<MaxSize;i++)
{
if(L->used[i] == 0)
{
cout<<endl<<"找到空闲空间:"<<i<<endl;
L->used[i] = 1;
q = i;
break;
}
}
while(L->Data[pos].data!= element)
{
last = pos;
pos = L->Data[pos].next;
}//pos = 5, last = 1
L->Data[last].next = q;
L->Data[q].next = pos;
L->Data[q].data = e;
}
操作如下：
void deleteElement(StatickLinkPtr &L,int e)
{
int pos = 0,q;
while((L->Data[pos].data != null) && (L->Data[L->Data[pos].next].data != e))
{
pos = L->Data[pos].next;
}//pos是目标节点的上一个结点的指针域，即目标结点的下标
q = L->Data[pos].next;//目标结点的下标
L->Data[pos].next = L->Data[L->Data[pos].next].next;//目标结点的下一个结点的下标 由 目标结点的上一个结点的指针域指向
L->used[q] = 0;
}
删除元素3：
void PrintStaticLink(StatickLinkPtr &L)
{
int pos = 0;
cout<<endl<<"静态链表打印:"<<endl;
while(pos != -1)
{
cout<<L->Data[pos].data<<" ";
pos = L->Data[pos].next;
}
cout<<endl;
}
bool DestroyStaticlinkList(StatickLinkPtr &L)
{
if(!L)
return false;
int pos = 0;
for(int i = 0;i<MaxSize;i++)
{
L->used[i] = 0;
}
return true;
}
#include <iostream>
using namespace std;
#define null -1
#define MaxSize 8
typedef struct _StatickLinkNode
{
int data;
int next;
}StackLinkNode;
typedef struct _StatickLink
{
StackLinkNode *Data;
int *used;
}StaticLink,*StatickLinkPtr;
bool initStaticLink(StatickLinkPtr &L)
{
L = new StaticLink;
L->Data = new StackLinkNode[MaxSize];
L->used = new int[MaxSize];
if(!L||!L->Data||!L->used)
return false;
L->Data[0].data = 0;
L->Data[0].next = null;
L->used[0] = 1;
for(int i=1;i<MaxSize;i++)
{
L->used[i] = 0;
}
return true;
}
void InsertByTail(StatickLinkPtr &L,int e)
{
int pos = 0,i,q = 1,r=0;
//查找最后一个结点
while(pos != -1)
{
r = pos;//r记录尾结点的下标
pos = L->Data[r].next;
}//pos = 3
for(i = 1;i<MaxSize;i++)
{
if(L->used[i] == 0)
{
cout<<endl<<"找到空闲空间:"<<i<<endl;
L->used[i] = 1;
q = i;
break;
}
}
if(pos>=MaxSize || i>=MaxSize)
{
cout<<"无法在尾部插入！！"<<endl;
return;
}
L->Data[q].data = e;//新的尾结点的数据域存放新的数据
L->Data[q].next = null;//指针域为-1，成为新的尾结点
L->Data[r].next = q; // 原来的尾结点的指针域，指向新的尾结点
}
void insertElementByData(StatickLinkPtr &L,int e,int element)// 新元素值 目标结点的元素值
{
int pos = 0,i,q,last=0;
for(i = 1;i<MaxSize;i++)
{
if(L->used[i] == 0)
{
cout<<endl<<"找到空闲空间:"<<i<<endl;
L->used[i] = 1;
q = i;
break;
}
}
while(L->Data[pos].data!= element)
{
last = pos;
pos = L->Data[pos].next;
}//pos = 5, last = 1
L->Data[last].next = q;
L->Data[q].next = pos;
L->Data[q].data = e;
}
void deleteElement(StatickLinkPtr &L,int e)
{
int pos = 0,q;
while((L->Data[pos].data != null) && (L->Data[L->Data[pos].next].data != e))
{
pos = L->Data[pos].next;
}//pos是目标节点的上一个结点的指针域，即目标结点的下标
q = L->Data[pos].next;//目标结点的下标
L->Data[pos].next = L->Data[L->Data[pos].next].next;//目标结点的下一个结点的下标 由 目标结点的上一个结点的指针域指向
L->used[q] = 0;
}
void PrintStaticLink(StatickLinkPtr &L)
{
int pos = 0;
cout<<endl<<"静态链表打印:"<<endl;
while(pos != -1)
{
cout<<L->Data[pos].data<<" ";
pos = L->Data[pos].next;
}
cout<<endl;
}
bool DestroyStaticlinkList(StatickLinkPtr &L)
{
if(!L)
return false;
int pos = 0;
for(int i = 0;i<MaxSize;i++)
{
L->used[i] = 0;
}
return true;
}
void Test()
{
StatickLinkPtr L = NULL;
StatickLinkPtr s = NULL;
//1.初始化
if(initStaticLink(L))
cout<<"初始化成功！！！"<<endl;
else
cout<<"初始化失败！！！"<<endl;
//2.尾插法
int num = 0;
cout<<"请输入尾部插的次数:";
cin>>num;
cout<<"请依次输入"<<num<<"个元素：";
while(num>0)
{
int data;
cin>>data;
InsertByTail(L,data);
num--;
}
PrintStaticLink(L);
InsertByTail(L,7);
PrintStaticLink(L);
//3.删除结点
cout<<"请输入要删除的元素:";
int data;
cin>>data;
deleteElement(L,data);
PrintStaticLink(L);
InsertByTail(L,8);
PrintStaticLink(L);
//4，按值插入
insertElementByData(L,11,2);
PrintStaticLink(L);
//5.摧毁静态链表
if(DestroyStaticlinkList(L))
cout<<endl<<"摧毁成功！"<<endl;
}
int main()
{
Test();
system("pause");
return 0;
}
